Fundamental Data Structures: Stacks (3.2.4)
Welcome to the fascinating world of data structures! We've already looked at structures like Arrays and Lists. Now, we dive into Stacks—one of the simplest, yet most fundamentally important, data structures in Computer Science.
Understanding stacks isn't just about memorising terms; it's about grasping how many critical computer processes, from managing subroutines to handling 'Undo' features, rely on this simple concept. Don't worry if this seems tricky at first; we'll break it down using everyday analogies!
1. The Last-In, First-Out (LIFO) Principle
The single most important characteristic of a stack is its strict ordering principle: Last-In, First-Out (LIFO).
Imagine a stack of freshly washed plates in a café dispenser.
- When a new plate is added, it goes on top. (Last In).
- When a chef needs a plate, they take the one from the top. (First Out).
If you added plates A, then B, then C:
[A is at the bottom, C is at the top.]
When you remove a plate, C must come off before B, and B must come off before A.
Memory Aid: LIFO
Last In, First Out. Think of a Stack of Plates (S & P)!
A Stack is a data structure where insertion and deletion can only happen at one end, which we call the Top. This enforces the LIFO rule.
2. Core Stack Operations
The syllabus requires you to know and apply three main operations used on stacks, plus the essential checks required when implementing them.
Push (Adding an item)
The operation to add a new item to the top of the stack is called Push.
Step-by-step:
1. Check if the stack is full (we can't push if there's no space!).
2. If not full, place the new item onto the current top position.
3. Update the pointer/index that tracks the Top of the stack.
Example: Pushing 'Apple' onto a stack of fruits means 'Apple' is now the new top item.
Pop (Removing an item)
The operation to remove and return the item currently at the top of the stack is called Pop.
Step-by-step:
1. Check if the stack is empty (we can't pop if there's nothing there!).
2. If not empty, retrieve the item from the top position.
3. Update the pointer/index to move the Top down (effectively removing the item).
Crucially, the Pop operation removes the item, reducing the size of the stack.
Peek (or Top) (Viewing the top item)
The Peek (sometimes called Top) operation returns the value of the top element without removing it from the stack.
Analogy: Lifting the top plate slightly to read the label underneath, then placing it back down.
Do not confuse Pop and Peek. Pop changes the stack; Peek only reads the stack.
3. Implementing a Stack using a One-Dimensional Array
Although modern programming languages often have built-in Stack libraries, you must understand how a stack is created "under the hood," typically using a one-dimensional array.
The Stack Pointer (Top of Stack)
When using an array (which has a fixed size), we need a variable, usually called the Stack Pointer (or Top Of Stack), to keep track of where the LIFO operations (Push/Pop) should occur.
This pointer holds the index (position) of the element most recently added.
Checking if the Stack is Empty or Full
Since an array has a fixed capacity, checking for boundary conditions is essential to prevent errors (like trying to push onto a full stack, known as Stack Overflow).
- Is Empty?: The stack is empty if the Stack Pointer is at its initial position. If we define the array indices starting at 0, the pointer is typically initialised to -1 when the stack is empty. If the pointer equals the empty index, the stack is empty.
- Is Full?: The stack is full if the Stack Pointer has reached the maximum allowable index of the underlying array. If the array size is N, the maximum index is \(N-1\).
Let's trace a stack with a maximum size of 5 (indices 0 to 4).
Initial state: Stack Pointer (SP) = -1.
- Push Item A: SP increments to 0. A is stored at index 0.
- Push Item B: SP increments to 1. B is stored at index 1.
- Push Item C: SP increments to 2. C is stored at index 2.
- (Stack Array: [A, B, C, _, _]. SP = 2)
- Pop: Retrieve item at index 2 (C). SP decrements to 1.
- (Stack Array: [A, B, _, _, _]. SP = 1)
- Peek: Retrieve item at index 1 (B). SP remains 1.
Key Takeaway on Implementation
Implementing a stack via an array requires managing the Stack Pointer. PUSH involves incrementing the pointer and storing the data; POP involves retrieving the data and decrementing the pointer. Crucial checks are needed to ensure the pointer doesn't go below the minimum index (empty) or above the maximum index (full).
4. Applications of Stacks in Computer Science
Stacks are not just theoretical; they are fundamental building blocks for many critical computing processes. You must be able to describe situations where a stack is an appropriate data structure.
A. Subroutine Call Stack (The Most Important Use!)
When a program executes, the system uses a stack (the Call Stack) to manage function/subroutine calls.
- When Subroutine A calls Subroutine B, the system must remember where to return to in A when B finishes. This information (the return address), along with any parameters and local variables (collectively known as the Stack Frame), is Pushed onto the call stack. (This links directly to section 3.1.2.7 of the syllabus!)
- When Subroutine B completes, its stack frame is Popped, and the program uses the stored return address to jump back to the correct spot in A.
This LIFO process ensures that nested subroutines finish in the reverse order they were called.
B. The 'Undo' Feature
In word processors (like Microsoft Word) or graphic editors (like Photoshop), the 'Undo' functionality relies on a stack.
- Every action you perform (typing, drawing, deleting) is Pushed onto the undo stack.
- When you press 'Undo', the last action added is Popped off the stack and reversed.
C. Expression Evaluation
Stacks are used by compilers and interpreters to convert and evaluate mathematical expressions, especially when dealing with different formats like postfix (Reverse Polish Notation) or prefix notation. Operands (numbers) are typically pushed, and when an operator is encountered, the necessary operands are popped, the calculation is done, and the result is pushed back.
Did you know?
The term "Stack Overflow", often seen as an error message or the name of a famous programming website, refers to what happens when the computer's internal call stack runs out of memory because too many functions are called without returning (often due to badly written recursive code without a base case!).
The stack is a LIFO structure defined by its operations: Push (add to top), Pop (remove from top), and Peek (look at top without removing).
In array implementation, a Stack Pointer tracks the top element. We must check if the stack is Empty (pointer at initial value) or Full (pointer at maximum array index) before performing Pop or Push, respectively.
Its primary use is managing Subroutine Call Stacks in system memory.
Keep practising these concepts, perhaps by simulating stack operations by hand or using your programming language's library implementation!