Does Ruby have containers like stacks, queues, linked-lists, maps, or sets?

Question

I checked several Ruby tutorials online and they seemed to use array for everything. So how could I implement the following data structures in Ruby?

• Stacks
• Queues
• Linked lists
• Maps
• Sets

Answer 1

There is also a great library Algorithms by Kanwei of data structures and algorithms with ~2.6K stars on Github.

require 'rubygems'
require 'algorithms'

stack = Containers::Stack.new
max_heap = Containers::MaxHeap.new

Installation:

gem install kanwei-algorithms

Answer 2

Don't use arrays for queues or stacks unless you understand the overheads of using arrays for your problems and you're ok with those overheads.

Arrays are intended to store a collection of items. They are not optimized for all stack and queue operations. Ruby just gives us the convenience of using arrays for queue- and stack-like operations. And this convenience comes with the price of a higher space or time complexity.

For example, shifting an array pointer instead of doing a proper pop increases the space complexity because it stores more data than actually required.

Or another example, rewriting your array instead of a proper push dramatically increases the time complexity because it requires moving each element of the array to another space on the disc.

Luckily, basic stacks are easily to implement. Here's an example:

class Node
  attr_accessor :val, :prev
  def initialize(val:, prev:)
    @val = val
    @prev = prev
  end
end

class Stack
  attr_reader :length

  def initialize()
    @head = nil
    @length = 0
  end

  def push(val)
    node = Node.new(val: val, prev: @head)
    @head = node
    @length += 1
  end
  alias << :push

  def pop
    return nil unless @head
    pop_node = @head
    @head = pop_node.prev
    @length -= 1
    pop_node.val
  end
end

Usage example:

s = Stack.new
=> #<Stack:0x00007fd682045ed8 @head=nil, @length=0>
s.push 1
=> 1   # stack = [1]
s.push "2"
=> 2   # stack = [1, "2"]
s.push 3
=> 3   # stack = [1, "2", 3]
s.length
=> 3
s.pop
=> 3   # stack = [1, "2"]
s.pop
=> "2" # stack = [1]
s.pop
=> 1   # stack = []
s.length
=> 0
s.pop
=> nil

You can also add any other operation required by your use case like peek or empty? pretty easily.

Answer 3

Heaps/ Priority Queue A min heap/priority queue functionality can be achieved using sorted set.

Creation(Adding data to heap/PQ)

pq = SortedSet.new([3]) #=> #<SortedSet: {3}>
pq.add(1) #=> #<SortedSet: {1, 3}>
pq.add(6) #=> #<SortedSet: {1, 3, 6}>

Deletion(top priority element)

top = pq.first #1
pq.delete(top) #=> #<SortedSet: {3, 6}>, top is '1'
top = pq.first #3
pq.delete(top) #=> #<SortedSet: {6}>

Answer 4

I guess most of it is covered in above answers but just for summing it up for a better explanation:

Stack:

stack = []
stack << 2 # push 2 => stack = [2]
stack << 3 # push 3 => stack = [2, 3]
stack.pop  # pop => 3, stack = [2]

Queue:

# we have a Queue class
queue = Queue.new
queue << 2 # push 2 => queue = [2]
queue << 3 # push 3 => queue = [2, 3] (just a representation, it will be an object though)
queue.pop # pop 2

Linked List:

# A very simple representation
class Node
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

class LinkedList

  def initialize(value)
    @head = Node.new(value)
  end

  def add(value)
    current = @head
    while !current.next_node.nil?
      current = current.next_node
    end
    current.next_node = Node.new(value)
  end
end

ll = LinkedList.new
ll.add(10)
ll.add(20)

Maps:

# Hash incase of ruby
a = {} (or a = Hash.new)
a['one'] = 1 # a = {"one"=>1}
a['two'] = 2 # a = {"one"=>1, "two"=>2}

Set:

# we have a Set class
require 'set'
s = Set.new         # <Set: {}>
s.add(1)            # <Set: {1}>
s.add(2)            # <Set: {1, 2}>
s.add(1)            # <Set: {1, 2}>
s.instance_of?(Set) # true

Answer 5

(Moved from Comment)

Well, an array can be a stack or queue by limiting yourself to stack or queue methods (push, pop, shift, unshift). Using push / pop gives LIFO(last in first out) behavior (stack), while using push / shift or unshift / pop gives FIFO behavior (queue).

Maps are hashes, and a Set class already exists.

You could implement a linked list using classes, but arrays will give linked-list like behavior using the standard array methods.

Answer 6

I would like to add Deque implementation (which is more generic in linear DS usage) in Ruby :

class Node
  attr_accessor :value, :next, :prev
  def initialize(value, next_node, prev_node)
    @value = value
    @next = next_node
    @prev = prev_node
  end
end


class Deque
  attr_accessor :start, :end
  def initialize
    @start = @end = nil
  end

  def push_back(val)
    if @start.nil?
      @start = @end = Node.new(val, nil, nil)
    else
      @end.next = Node.new(val, nil, @end)
      @end.next.prev = @end
      @end = @end.next
    end
  end

  def pop_back
    if @start == @end #only one node
      @start = @end = nil
    else
      @end = @end.prev
      @end.next = nil
    end
  end

  def push_front(val)
    @start.prev = Node.new(val, @start, nil)
    @start = @start.prev
  end

  def pop_front
    if @start == @end #only one node
      @start = @end = nil
    else
      @start = @start.next
      @start.prev.next = nil
      @start.prev = nil
    end
  end

  def empty?
    @start.nil? && @end.nil?
  end

  def front
    @start.value unless self.empty?
  end

  def back
    @end.value unless self.empty?
  end

  def print(node)
    arr = []
    while node
      arr << node.value
      node = node.next
    end
    p arr
  end
end


q = Deque.new
q.push_back(1)
q.push_back(2)
q.push_back(3)
q.push_back(4)
q.print(q.start)
q.push_front(0)
q.push_front(-1)
q.print(q.start)
q.pop_back()
q.pop_back()
q.print(q.start)
q.pop_front()
q.pop_front()
q.print(q.start)
p q.front
p q.back

Output :

[1, 2, 3, 4]
[-1, 0, 1, 2, 3, 4]
[-1, 0, 1, 2]
[1, 2]
1
2

Answer 7

The Ruby language actually has a Queue class which can be used as .... wait for it... a Queue ;)

It is thread safe and easy to use.

The rest of @James answer is great and accurate.

Answer 8

Yes, although not expressly in name. The Array class can be used as a stack, queue, or linked list. For example, push and pop make it behave like a stack. Ruby's Map is the Hash class. Ruby also has a Set class, although you have to import a module to use it (require 'set').