Data Structures: Queues

I.Conceptual

What is the queue?

queue A given queue is a linear data structure that is open at both ends and it contains an ordered data set.

Queues provide three methods for interaction:

Enqueue: adds data to the end of the queue
Dequeue: get the first element out of the queue
Peek: provide the data of the first element of the queue without deleting it.

queue You can think of this data structure like a line of people queuing up to buy movie tickets.

Each person has a name(data) , when a person lines up in an empty row they are the first in the row.

Those who come later will be placed behind the person who came before them or at the end of the line (enqueue).

When a cashier serves someone, they start at the front of the line. Each person served is priced from the front of the line, they buy a ticket and leave (dequeue).

If they just want to know who is next in line, they can go through and get their name without removing them from the queue(peek).

Queues are a First In, First Out(FIFO).

Some other special points:

Enqueueing onto a full queue causes a queue overflow
If you attempt to dequeue data from an empty queue, it will result in a queue underflow.
Can be implemented using a linked list or array
One last constraint that may be placed on a queue is its length. If a queue has a limit on the amount of data that can be placed into it, it is considered a bounded queue.
Since both the head and tail of the queue must be accessed, a reference to both the nodes head and its tail must be maintained.

II. Ideas

We can implement queue using linked list or array, below we will implement it using array:

First, create a Queue class
Next, inside it:
- Create a constructor that takes two parameters as size and a value initialized with nil.
- Inside constructor: Create an instance variable to store the size and an array to receive initialization value ==> the queue is currently empty.
Next, we will create methods to build a real queue:
- enqueue: will allow us to add a new node to the end of the queue
- dequeue: will allow us to remove a node from the head of the queue and return its value
- peek: will allow us to see the value of the top of the queue without having to clear it
- We’ll also set up some helper methods that will help us keep track of the queue size to prevent “overflowing” and “overflowing” queues.
- One more method to display our queue.

III. Iplementation

The idea is done, let’s put into practice!

Since ruby has built-in methods, we can use it easily.

class SuperQueue
  class OverflowException < StandardError; end
  class UnderflowException < StandardError; end
  attr_accessor :size

  def initialize(size: 5, initial_value: nil)
    @size = size
    @arr = [initial_value]
  end

  def enqueue(value)
    raise OverflowException.new("the queue is full") if size <= @arr.length 

    @arr.append(value)  
  end
 
  def dequeue
    raise UnderflowException.new("the queue is empty") if @arr.length == 0 

    @arr.shift
  end

  def display 
    puts "#{@arr}" 
  end

  def peek
    @arr.first
  end
end

Let’s try it

queue = SuperQueue.new(size: , initial_value: 1)
puts "Queue size: #{queue.size}"

queue.enqueue(2)
queue.enqueue(3)
puts "------------"
queue.print
puts queue.peek


puts "dequeued time #1: #{queue.dequeue}"
puts "dequeued time #2: #{queue.dequeue}"
puts "dequeued time #3: #{queue.dequeue}"

puts "Print when queue is empty: \n"
queue.print

#queue.dequeue
# => Expectation raises UnderflowException

queue.enqueue(4)
queue.enqueue(5)
queue.enqueue(6)
queue.enqueue(7)
queue.enqueue(8)
queue.print

#queue.enqueue(9)
# => Expectation raises OverflowException

Output

Queue size: 5
------------
[1, 2, 3]
1
dequeued time #1: 1
dequeued time #2: 2
dequeued time #3: 3
Print when queue is empty:
[]
[4, 5, 6, 7, 8]
4

We will update the queue implementation using linked list in the near future. Please wait!

IV. Recap

Queue is a data structure which contains an ordered set of data.

It contain data nodes

-Queues provide three methods for interaction:

Enqueue: adds data to the end of the queue
Dequeue: get the first element out of the queue
Peek: provide the data of the first element of the queue without deleting it
Queues process data First In, First Out (FIFO)
Can be implemented using a linked list or array
Bounded queues have a limited size.
Enqueueing onto a full queue causes a queue overflow
Taking an element from an empty queue causes underflow

Thanks for reading my post!

thanks

Data Structures: Linked List and Doubly Linked lis

Data Structures: Stack