Queues (Cambridge (CIE) A Level Computer Science): Revision Note

Implementing a queue

How do you program a queue?

• A queue is a linear ADT that follows the First In, First Out (FIFO) principle:

  • Enqueue: Add item to the back

  • Dequeue: Remove item from the front

  • Peek/front: Look at the front item without removing

  • isEmpty / isFull: Check queue status

• Assuming a record-based circular queue implementation:

Enqueue

PROCEDURE enqueue(q : REF Queue, item : STRING)
    IF NOT isFull(q) THEN
        q.rear ← (q.rear + 1) MOD q.capacity
        q.items[q.rear] ← item
        q.size ← q.size + 1
    ELSE
        OUTPUT "Queue is full"
    ENDIF
ENDPROCEDURE

Dequeue

FUNCTION dequeue(q : REF Queue) RETURNS STRING
    IF NOT isEmpty(q) THEN
        DECLARE value : STRING
        value ← q.items[q.front]
        q.front ← (q.front + 1) MOD q.capacity
        q.size ← q.size - 1
        RETURN value
    ELSE
        RETURN "Queue is empty"
    ENDIF
ENDFUNCTION

isEmpty / isFull

FUNCTION isEmpty(q : Queue) RETURNS BOOLEAN
    RETURN q.size = 0
ENDFUNCTION

FUNCTION isFull(q : Queue) RETURNS BOOLEAN
    RETURN q.size = q.capacity
ENDFUNCTION

Find (linear search)

FUNCTION find(q : Queue, target : STRING) RETURNS BOOLEAN
    DECLARE i : INTEGER
    DECLARE pos : INTEGER
    pos ← q.front

    FOR i ← 1 TO q.size
        IF q.items[pos] = target THEN
            RETURN TRUE
        ENDIF
        pos ← (pos + 1) MOD q.capacity
    NEXT i

    RETURN FALSE
ENDFUNCTION

Python

from collections import deque

class Queue:
    def __init__(self, capacity):
        self.items = deque()
        self.capacity = capacity

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

    def isFull(self):
        return len(self.items) == self.capacity

    def enqueue(self, item):
        if not self.isFull():
            self.items.append(item)
        else:
            print("Queue is full")

    def dequeue(self):
        if not self.isEmpty():
            return self.items.popleft()
        else:
            return "Queue is empty"

    def peek(self):
        if not self.isEmpty():
            return self.items[0]
        else:
            return None

    def find(self, target):
        return target in self.items

# Example usage
q = Queue(5)
q.enqueue("Alice")
q.enqueue("Bob")
q.enqueue("Charlie")
print("Front item:", q.peek())
print("Popped:", q.dequeue())
print("Is 'Bob' in queue?", q.find("Bob"))

Java

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();

        // Enqueue
        q.offer("Alice");
        q.offer("Bob");
        q.offer("Charlie");

        // Peek
        System.out.println("Front item: " + q.peek());

        // Dequeue
        System.out.println("Popped: " + q.poll());

        // Find
        System.out.println("Is 'Bob' in queue? " + q.contains("Bob"));
    }
}