Data Structure - Queue

1. Introduction to Queue

A queue is an ordered collection of elements where insertion occurs at one end (the rear) and deletion occurs at the other end (the front). The queue follows the FIFO (First In, First Out) principle.

Analogy: A queue of people at a ticket counter. The first person to join the queue is the first one to be served. New people join at the back, and service happens from the front.

Characteristics:

• Elements are added at the rear and removed from the front.
• The first element inserted is the first one to be removed.
• Queue is a linear data structure.
• Both ends of the queue are accessible (front and rear).

2. FIFO Principle

FIFO stands for First In, First Out. The element that has been in the queue the longest is removed first.

# Queue visualization (front on left, rear on right)
# Empty: []
# Enqueue 10: [10]
# Enqueue 20: [10, 20]
# Enqueue 30: [10, 20, 30]
# Dequeue:    [20, 30]  (removed 10)
# Dequeue:    [30]      (removed 20)

3. Basic Queue Operations

4. Queue Implementation using List

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None

    def rear(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def display(self):
        print("Queue (front to rear):", self.items)

Note: Using pop(0) for dequeue is O(n). A more efficient approach uses collections.deque.

5. Enqueue Operation

The enqueue operation adds an element at the rear of the queue.

def enqueue(self, item):
    self.items.append(item)
    print(f"Enqueued {item} to queue.")

Algorithm:

1. Accept the element to be added.
2. Append the element to the end of the list (rear).
3. Increment the size of the queue.

6. Dequeue Operation

The dequeue operation removes and returns the front element from the queue.

def dequeue(self):
    if self.is_empty():
        print("Queue is empty. Cannot dequeue.")
        return None
    item = self.items.pop(0)
    print(f"Dequeued {item} from queue.")
    return item

Algorithm:

1. Check if the queue is empty. If empty, return underflow error.
2. Remove and return the element at index 0 (front).
3. Decrement the size of the queue.

7. Front and Rear Operations

def front(self):
    if self.is_empty():
        print("Queue is empty.")
        return None
    return self.items[0]

def rear(self):
    if self.is_empty():
        print("Queue is empty.")
        return None
    return self.items[-1]

8. Menu-Driven Queue Program

def menu():
    q = Queue()
    while True:
        print("\n--- QUEUE MENU ---")
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Front")
        print("4. Rear")
        print("5. Display")
        print("6. Size")
        print("7. Exit")
        choice = int(input("Enter choice: "))

        if choice == 1:
            item = input("Enter item to enqueue: ")
            q.enqueue(item)
        elif choice == 2:
            q.dequeue()
        elif choice == 3:
            print("Front element:", q.front())
        elif choice == 4:
            print("Rear element:", q.rear())
        elif choice == 5:
            q.display()
        elif choice == 6:
            print("Queue size:", q.size())
        elif choice == 7:
            print("Exiting...")
            break

9. Circular Queue

A circular queue overcomes the limitation of a linear queue where space at the front cannot be reused after dequeue operations. In a circular queue, the rear connects back to the front position.

Advantages:

• Efficient memory utilization.
• No need to shift elements.
• All positions in the array can be reused.

10. Circular Queue Implementation

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            print("Queue is full.")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty.")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        return item

11. Applications of Queue

• CPU scheduling: FCFS (First Come, First Served) scheduling in operating systems.
• Print spooling: Managing print jobs in the order they are submitted.
• Message queues: Communication between processes or services.
• Breadth-First Search (BFS): Graph traversal algorithm.
• Buffering: IO buffers, keyboard buffers.
• Call center systems: Managing customer calls in the order they arrive.
• Ticket booking systems: Processing requests in order.

12. Double-Ended Queue (Deque)

A deque (double-ended queue) allows insertion and deletion at both ends. Python provides the collections.deque class.

from collections import deque

dq = deque()
dq.append(10)       # Add to rear
dq.appendleft(20)    # Add to front
dq.pop()            # Remove from rear
dq.popleft()        # Remove from front

13. Priority Queue

A priority queue is a queue where each element has a priority. Elements with higher priority are dequeued before elements with lower priority.

import heapq

class PriorityQueue:
    def __init__(self):
        self.items = []

    def push(self, item, priority):
        heapq.heappush(self.items, (priority, item))

    def pop(self):
        return heapq.heappop(self.items)[1]

14. Stack vs Queue Comparison