Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
November 20, 2022 03:42 pm GMT

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.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.

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 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

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To