Queues

This lesson covers the queue — a fundamental Abstract Data Type that follows the First-In, First-Out (FIFO) principle. Queues are used in many computing applications, from printer spooling to process scheduling. This lesson covers linear, circular, and priority queues.

---

What is a Queue?

A queue is an ordered collection of elements where:

• Items are added (enqueued) at the rear (back) of the queue.
• Items are removed (dequeued) from the front of the queue.
• The first item added is the first to be removed — FIFO.

Think of a queue at a shop: the first person to join is the first to be served.

FRONT → [ 10 | 20 | 30 | 40 ] ← REAR
         ↑ dequeue here          ↑ enqueue here

---

Queue Operations

Operation	Description	Time Complexity
enqueue(item)	Add an item to the rear.	O(1)
dequeue()	Remove and return the item from the front.	O(1)
front() / peek()	View the front item without removing it.	O(1)
isEmpty()	Check whether the queue is empty.	O(1)
isFull()	Check whether the queue is full (array-based only).	O(1)
size()	Return the number of items.	O(1)

---

Linear Queue (Array-Based)

A linear queue uses an array with front and rear pointers.

Problem with Linear Queues

As items are dequeued, the front pointer moves forward. The spaces at the beginning of the array become unusable, even though they are empty. This leads to wasted space and eventually the queue appears "full" when it is not.

Initial:    FRONT=0, REAR=3
            [ 10 | 20 | 30 | 40 | __ ]

After 2 dequeues: FRONT=2, REAR=3
            [ __ | __ | 30 | 40 | __ ]
            Wasted space!

---

Circular Queue

A circular queue solves the wasted-space problem by treating the array as if it wraps around. When the rear reaches the end of the array, it wraps back to the beginning (if there is space).

How It Works

The front and rear pointers wrap around using modular arithmetic:

next position = (current position + 1) MOD array_size

Pseudocode

CONSTANT MAX_SIZE = 5
DECLARE queue: ARRAY[0..MAX_SIZE-1] OF INTEGER
DECLARE front: INTEGER = 0
DECLARE rear: INTEGER = -1
DECLARE count: INTEGER = 0

PROCEDURE enqueue(item: INTEGER)
    IF count = MAX_SIZE THEN
        OUTPUT "Queue is full"
    ELSE
        rear = (rear + 1) MOD MAX_SIZE
        queue[rear] = item
        count = count + 1
    END IF
END PROCEDURE

FUNCTION dequeue() RETURNS INTEGER
    IF count = 0 THEN
        OUTPUT "Queue is empty"
        RETURN -1
    ELSE
        item = queue[front]
        front = (front + 1) MOD MAX_SIZE
        count = count - 1
        RETURN item
    END IF
END FUNCTION

Python Implementation

class CircularQueue:
    def __init__(self, max_size: int = 5):
        self.__queue = [None] * max_size
        self.__front = 0
        self.__rear = -1
        self.__count = 0
        self.__max_size = max_size

    def enqueue(self, item):
        if self.__count == self.__max_size:
            raise OverflowError("Queue is full")
        self.__rear = (self.__rear + 1) % self.__max_size
        self.__queue[self.__rear] = item
        self.__count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.__queue[self.__front]
        self.__front = (self.__front + 1) % self.__max_size
        self.__count -= 1
        return item