ADT Queue

A queue is a linear Abstract Data Type that holds items in the order they arrive and releases them in that same order. It follows the First-In, First-Out (FIFO) rule: the item that has waited longest is served next. Think of students lining up at the canteen — Musarrat joined first, so Musarrat is served first; anyone arriving later joins the back.

Because a queue is an abstract type, the syllabus does not care how you store it underneath — only that it behaves as FIFO. The two common implementations are a 1D array with two pointers (covered here) and a linked list.

A queue grows at the rear and shrinks at the front. Both pointers only ever move forward (to the right) in a basic linear queue. Watch them as three items are enqueued and one is dequeued:

This class stores items in a fixed list and keeps two integer pointers. A count is also kept so “empty” and “full” are trivial to test.

class Queue:
    def __init__(self, size=10):
        self.items = [None] * size   # fixed-size storage
        self.maxSize = size          # capacity
        self.front = -1              # next item to remove
        self.rear  = -1              # last item added

    def isEmpty(self):
        return self.front == -1

    def isFull(self):
        return self.rear == self.maxSize - 1

    def enqueue(self, item):
        if self.isFull():
            return "Queue Overflow"
        if self.front == -1:         # first item
            self.front = 0
        self.rear += 1               # advance rear, then store
        self.items[self.rear] = item

    def dequeue(self):
        if self.isEmpty():
            return "Queue Underflow"
        item = self.items[self.front]
        self.items[self.front] = None
        if self.front == self.rear:  # last item just left
            self.front = self.rear = -1
        else:
            self.front += 1          # advance front
        return item

    def peek(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.items[self.front]

Enqueue (insert at the rear) — Cambridge pseudocode:

PROCEDURE Enqueue(NewItem)
    IF Length = MaxLength THEN
        OUTPUT "Queue full"
    ELSE
        Rear <- Rear + 1
        IF Rear > MaxLength - 1 THEN   // wrap (circular)
            Rear <- 0
        ENDIF
        Queue[Rear] <- NewItem
        IF Front = -1 THEN
            Front <- 0
        ENDIF
        Length <- Length + 1
    ENDIF
ENDPROCEDURE

Dequeue (remove from the front) — Cambridge pseudocode:

FUNCTION Dequeue() RETURNS STRING
    IF Length = 0 THEN
        RETURN ""                 // empty / null
    ENDIF
    ThisItem <- Queue[Front]
    Front <- Front + 1
    IF Front > MaxLength - 1 THEN // wrap (circular)
        Front <- 0
    ENDIF
    Length <- Length - 1
    RETURN ThisItem
ENDFUNCTION

In a linear queue both pointers march to the right and never come back. After several dequeues the slots at the start are empty but unusable — rear can hit the end of the array and report “full” even though half the queue is free. We call this pointer drift or wasted space.

The circular queue fixes exactly this — pointers wrap back to index 0 so freed slots are reused.

A circular queue treats the array as a ring: when a pointer would step past the last index, it wraps back to index 0 using modulo arithmetic (pointer + 1) MOD maxSize. Freed slots at the start are reused, so no space is wasted. A count variable tells full from empty (both can have front == rear).

class CircularQueue:
    def __init__(self, size=10):
        self.queue = [None] * size
        self.maxSize = size
        self.head = 0       # front
        self.tail = 0       # rear (next free slot)
        self.count = 0      # items currently stored

    def is_full(self):
        return self.count == self.maxSize

    def is_empty(self):
        return self.count == 0

    def enqueue(self, item):
        if self.is_full():
            return "Queue is full"
        self.queue[self.tail] = item
        self.tail = (self.tail + 1) % self.maxSize   # wrap-around
        self.count += 1

    def dequeue(self):
        if self.is_empty():
            return "Queue is empty"
        item = self.queue[self.head]
        self.queue[self.head] = None
        self.head = (self.head + 1) % self.maxSize   # wrap-around
        self.count -= 1
        return item

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python/pseudocode solution.