Queues

This lesson covers queues — a fundamental abstract data type (ADT) following the FIFO principle. Queues appear extensively in the OCR A-Level Computer Science (H446) specification and have many practical applications in computing.

---

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first item added is the first item to be removed — like a queue of people waiting in line.

Real-World Analogies

• A queue at a supermarket checkout: first person in line is served first.
• Print jobs: the first document sent to the printer is printed first.
• Customer service calls: callers are answered in the order they called.

---

Queue Operations

Operation	Description	Time Complexity
enqueue(item)	Add an item to the rear of the queue	O(1)
dequeue()	Remove and return the item at the front	O(1)
front() / peek()	Return 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)	O(1)
size()	Return the number of items in the queue	O(1)

---

Linear Queue (Array-Based)

A linear queue uses an array with a front pointer and a rear pointer.

Pseudocode (OCR Style)

const MAX_SIZE = 5
array queue[MAX_SIZE]
front = 0
rear = -1
count = 0

function enqueue(item)
    if count == MAX_SIZE then
        print("Queue Full")
    else
        rear = rear + 1
        queue[rear] = item
        count = count + 1
    end if
end function

function dequeue()
    if count == 0 then
        print("Queue Empty")
        return null
    else
        item = queue[front]
        front = front + 1
        count = count - 1
        return item
    end if
end function

Problem with Linear Queues

As items are dequeued, the front pointer moves forward, leaving wasted space at the beginning of the array that can never be reused. Eventually, the rear pointer reaches the end of the array even though there is free space at the front.

After several enqueue/dequeue operations:
[ _ | _ | C | D | E ]
  ^front=0 has moved, spaces at indices 0,1 are wasted
Actually:
front=2, rear=4 — no room to enqueue even though indices 0 and 1 are empty

---

Circular Queue

A circular queue solves the wasted space problem by treating the array as a circle — when the rear pointer reaches the end, it wraps around to the beginning.

The Key Formula

next position = (current position + 1) MOD max_size

This formula wraps the pointer around. For example, in a queue of size 5:

• (4 + 1) MOD 5 = 0 (wraps from index 4 back to index 0)

Pseudocode (OCR Style)

const MAX_SIZE = 5
array queue[MAX_SIZE]
front = 0
rear = -1
count = 0

function enqueue(item)
    if count == MAX_SIZE then
        print("Queue Full")
    else
        rear = (rear + 1) MOD MAX_SIZE
        queue[rear] = item
        count = count + 1
    end if
end function

function dequeue()
    if count == 0 then
        print("Queue Empty")
        return null
    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):
        self.queue = [None] * max_size
        self.max_size = max_size
        self.front = 0
        self.rear = -1
        self.count = 0

    def enqueue(self, item):
        if self.count == self.max_size:
            raise OverflowError("Queue Full")
        self.rear = (self.rear + 1) % self.max_size
        self.queue[self.rear] = item
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("Queue Empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.max_size
        self.count -= 1
        return item