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.
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"]
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.
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
5
6
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)
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>'
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>'
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)