Stacks and Queues

Overview

Stacks and Queues are fundamental Abstract Data Types (ADTs) that appear consistently in the Edexcel A-Level Computer Science exam. While seemingly simple, they are the building blocks for complex operations like managing subroutine calls, scheduling tasks in an operating system, and handling data buffers. An ADT is defined by its behaviour—the operations it supports—rather than its specific implementation. For the exam, you must be proficient in implementing these structures using both static arrays and dynamic linked lists, and be able to articulate the trade-offs between these methods. Examiners frequently test candidates on their ability to trace algorithms, write pseudocode for core operations (Push, Pop, Enqueue, Dequeue), and explain the mechanics of circular queues and the call stack. Mastering this topic is not just about memorising algorithms; it’s about understanding why they work and how they are applied in real-world systems, which is key to hitting the higher AO2 and AO3 assessment objectives.

Key Concepts

Concept 1: The Stack (LIFO)

A stack operates on a Last-In, First-Out (LIFO) principle. The last item added to the stack is the first one to be removed. Think of it as a stack of plates in a canteen; you add a plate to the top and you take a plate from the top.

• Push: Adds an item to the top of the stack.
• Pop: Removes the item from the top of the stack.
• Peek (or Top): Returns the top item without removing it.
• isEmpty: Checks if the stack has no items.
• isFull: Checks if the stack has reached its maximum capacity (only relevant for static implementations).

Examiners award marks for explicitly checking isFull before a Push and isEmpty before a Pop. This demonstrates robust algorithmic thinking.

Static Implementation (Array): A static stack uses a fixed-size array and a pointer, typically called Top, which tracks the index of the top element. Top is often initialised to -1 to indicate an empty stack. This implementation is fast (O(1) for all operations) but risks overflow if the number of items exceeds the array size.

Dynamic Implementation (Linked List): A dynamic stack uses a linked list of nodes. Each node contains data and a pointer to the next node. The Top pointer simply holds the memory address of the head node. This is more flexible as it only uses as much memory as needed and won't overflow unless the entire system runs out of memory (heap overflow). However, it has slightly higher memory overhead due to storing pointers.

Concept 2: The Queue (FIFO)

A queue operates on a First-In, First-Out (FIFO) principle. The first item added to the queue is the first one to be removed. This is analogous to a queue of people at a bus stop.

• Enqueue: Adds an item to the rear of the queue.
• Dequeue: Removes the item from the front of the queue.
• isEmpty / isFull: Used for checking the state of the queue.

Linear Queue: In a static array implementation, a linear queue uses two pointers: Front (or Head) and Rear (or Tail). As items are dequeued, the Front pointer moves forward, leaving unused space at the beginning of the array. This is inefficient and can lead to a state where the queue reports as full (Rear is at the end) even when there are empty slots.

Concept 3: The Circular Queue

A circular queue elegantly solves the inefficiency of a linear queue by treating the array as a ring. When a pointer reaches the end of the array, it wraps around to the beginning. This is achieved using modulo arithmetic.

Mathematical/Scientific Relationships

The most critical formula for this topic, which you must memorise, is the pointer update for a circular queue:

• To add an item (enqueue): Rear = (Rear + 1) MOD MaxSize
• To remove an item (dequeue): Front = (Front + 1) MOD MaxSize

Here, MaxSize is the total number of slots in the array. This single line of logic is worth marks in almost every circular queue pseudocode question. Forgetting to use MOD and simply incrementing the pointer is a common mistake that leads to array index out of bounds errors.

Practical Applications

• Stacks: Used extensively for managing function calls (the call stack), parsing expressions in compilers (infix to postfix conversion), and implementing undo/redo features in software like text editors.
• Queues: Used for managing tasks in operating systems (print queues, CPU scheduling), handling data buffers in network communications, and in breadth-first search algorithms in graphs.