The Queue Data Strucure and How to Implement a Queue in Ruby
Tags: ruby, webdev, tutorial, algorithms
Published: 2022-11-20 15:42:59

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gdcjxtow1li3r8ysnzoq.png)

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:

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


![mmmm syntax sugar](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/db7f956qjkt819owg19b.png)


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.

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

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

```ruby
queue = SizedQueue.new(5)
```

```ruby
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: 

```ruby
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!