Implementing Queues

In this post, we will dive into the implementation details of queues, discussing the two common approaches - array-based and linked list-based implementations. We will explore the enqueue and dequeue operations and provide code examples in popular programming languages.

Overview of Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added to the back of the queue and removed from the front. Just like in a real-life queue, the element that is added first will be the first one to be removed.

Queues have two primary operations:

1. Enqueue operation: Adds an element to the back of the queue.
2. Dequeue operation: Removes an element from the front of the queue.

Queues are commonly used in scenarios where the order of processing matters, such as task scheduling, printer spooling, and breadth-first search algorithms.

Array-based Implementation

One way to implement a queue is by using an array. We will maintain two pointers - front and rear - to keep track of the front and back of the queue, respectively.

The enqueue operation is straightforward. We simply add the element at the rear and increment rear by 1. However, we need to consider scenarios where the queue is full, known as queue overflow.

The dequeue operation involves removing the element at the front and moving the front pointer forward. Similar to the enqueue operation, we need to handle scenarios where the queue is empty, known as queue underflow.

Here is an example of an array-based queue implementation in Python:

class Queue:
   def __init__(self, capacity):
      self.queue = []
      self.capacity = capacity
      self.front = 0
      self.rear = -1
   
   def enqueue(self, item):
      if self.rear == self.capacity - 1:
         print("Queue is full!")
         return
      self.rear += 1
      self.queue.append(item)
      
   def dequeue(self):
      if self.front > self.rear:
         print("Queue is empty!")
         return None
      item = self.queue[self.front]
      self.front += 1
      return item

Linked List-based Implementation

Another approach to implementing a queue is by using a linked list. In this implementation, each node of the linked list will contain the data and a reference to the next node.

Similar to the array-based implementation, we maintain two pointers - front and rear. The rear pointer will always point to the last node in the queue, and the front pointer will point to the first node.

Enqueueing an element involves creating a new node and adding it to the rear of the linked list. Dequeueing an element involves removing the first node, so the front pointer moves forward.

Here is an example of a linked list-based queue implementation in Java:

class Node {
   int data;
   Node next;
   
   public Node(int data) {
      this.data = data;
      this.next = null;
   }
}

class Queue {
   private Node front, rear;
   
   public Queue() {
      this.front = this.rear = null;
   }
   
   public void enqueue(int item) {
      Node newNode = new Node(item);
      if (this.rear == null) {
         this.front = this.rear = newNode;
         return;
      }
      this.rear.next = newNode;
      this.rear = newNode;
   }
   
   public int dequeue() {
      if (this.front == null) {
         System.out.println("Queue is empty!");
         return -1;
      }
      int item = this.front.data;
      this.front = this.front.next;
      if (this.front == null)
         this.rear = null;
      return item;
   }
}

Conclusion

Implementing queues can be achieved using array-based or linked list-based approaches. Both have their strengths and weaknesses, based on the specific requirements of use cases. Understanding the implementations and their operations is crucial for efficiently using queues in practical applications.