Stacks and Queues — Edexcel A-Level Study Guide

 ## 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.