An Interest In:
Web News this Week
- March 20, 2024
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
- March 14, 2024
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.
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.newqueue.unshift "apple"queue.unshift "orange"queue.unshift "banana"# queue is: ["apple", "orange", "banana"]queue.last # peek returns "dog"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 q1queue = Queue.newqueue.push(5)queue.push(6)#Prints the elementputs queue.popputs queue.pop
56
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 fullqueue.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!
Original Link: https://dev.to/jaredm/the-queue-data-strucure-and-how-to-implement-a-queue-in-ruby-433
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To