DEV Community

Cover image for The Queue Data Strucure and How to Implement a Queue in Ruby
professorjrod
professorjrod

Posted on • Updated on

The Queue Data Strucure and How to Implement a Queue in Ruby

If you don't already know what a queue is, it's quite simple.

I'm sure all of us have been in queues before-- like at the grocery store or bank. The person in the front of the line is helped first, then the second person, then third, and so forth.

a REAL queue

The exact same concept is what defines a queue in computer science.

The queue data structure always behaves like a real queue. The element that was inserted first will always be removed from the queue first. A common term for this is First in First Out (FIFO).

How can we implement a queue in Ruby?

You can use an array as a queue in ruby if you use certain Array methods

  • Array#unshift

  • Array#pop

Example:



queue = Array.new
queue.unshift "apple"
queue.unshift "orange"
queue.unshift "banana"

# queue is: ["apple", "orange", "banana"]

queue.last  # peek returns "banana"

queue.pop # "banana"
queue.pop # "orange"

# queue is: ["apple"]


Enter fullscreen mode Exit fullscreen mode

Here we use Array#unshift to add an element to the queue. Array#pop removes the first element from the queue, and Array#last peeks at the first element.

There are some other useful methods like Array#size and Array#empty? that are commonly used by developers for queues.

Built-in Queue Class

If you are a syntax sugar eater like myself (Ruby 4 lyfe), you will be happy to learn that Ruby has a built-in Queue class.

mmmm syntax sugar

Unlike the array implementation from before, the Ruby Queue class is thread-safe and commonly used for coordinating work in multi-threaded programs.

It is especially useful in threaded programming when information must be exchanged safely between multiple threads. Ruby's Queue has many methods that are more are less the same as Array.

It has similar methods to add elements to the back of the queue, such as #push, #enq, and #<< (the shovel).

It also has similar methods as the Array class to remove elements from the queue like #pop, #deq, and #shift.



#Create a new QUEUE q1
queue = Queue.new
 
queue.push(5)
queue.push(6)
 
#Prints the element
             puts queue.pop
                 puts queue.pop


Enter fullscreen mode Exit fullscreen mode


5
6


Enter fullscreen mode Exit fullscreen mode

You can see here that the Queue methods are basically exactly the same as Array, but there is some built0in magic behind the scenes in order for multi-threading to work.

For instance jn the example above, calling pop again to the empty queue will put your current thread to sleep & wait until something is added to the queue.

The SizedQueue

The SizedQueue in Ruby is the same as the regular Queue class but with a size limit, hence the name.

Whenever the queue is full, the push (and <<) methods will suspend the current thread until and item is taken off the queue



queue = SizedQueue.new(5)


Enter fullscreen mode Exit fullscreen mode


queue.push(:oranges)
queue.push(:apples)
queue.push(:blue)
queue.push(:orange)
queue.push(:green)
# At this point, the SizedQueue is full

queue.push(:throw_expection)
# data_structures/queues/queue.rb:81:in `push': No live threads left. Deadlock? (fatal)
# 1 threads, 1 sleeps current:0x00007ff54f407130 main thread:0x00007ff54f407130
# * #<Thread:0x00007ff54f86ef38 sleep_forever>
#    rb_thread_t:0x00007ff54f407130 native:0x000000010dd24dc0 int:0
#    data_structures/queues/queue.rb:81:in `push'
#    data_structures/queues/queue.rb:81:in `<main>'
#   from data_structures/queues/queue.rb:81:in `<main>'


Enter fullscreen mode Exit fullscreen mode

One useful thing about the sized queue is that you can choose to raise an exception, passing true as an argument like so:



queue.push(:throw_expection, true)
# data_structures/queues/queue.rb:83:in `push': queue full (ThreadError)
#   from data_structures/queues/queue.rb:83:in `<main>'


Enter fullscreen mode Exit fullscreen mode

And that's it! If you want, leave a comment and I will add some more Ruby implementations of the queue data structure. I hope this helped for my peeps out there studying Data Structures and Algorithms! HAPPY CODING!

Top comments (0)