Stacks (OCR A-Level Computer Science): Revision Notes
📚 Revision Notes
Stacks
Overview
A stack is a dynamic data structure that follows the Last In, First Out (LIFO) principle. This means the last item added to the stack is the first one to be removed. Stacks are commonly used in scenarios such as managing function calls, undoing operations in text editors, and navigating browser history.
Characteristics of a Stack
- Dynamic Data Structure: The size of the stack can grow or shrink dynamically as items are added or removed.
- LIFO Principle: The most recently added item is the first to be removed.
Key Operations
- Push: Adds an item to the top of the stack.
- Pop: Removes the item from the top of the stack.
- Peek: Returns the item at the top without removing it.
- IsEmpty: Checks if the stack is empty.
- IsFull (optional in static implementations): Checks if the stack has reached its maximum capacity.
Use Cases for Stacks
- Function Call Management: Stores return addresses when functions are called.
- Undo Mechanism: Tracks previous actions for easy reversal.
- Expression Evaluation: Converts infix expressions to postfix and evaluates them.
- Depth-First Search (DFS): Tracks visited nodes in a tree or graph traversal.
Implementation of Stacks
Dynamic Implementation Using a Linked List
A stack can be implemented using a linked list, where each node contains the data and a reference to the next node.
lightbulbExample
Example Pseudocode for Dynamic Stack:
CLASS Node
DATA value
POINTER next
CLASS Stack
POINTER top
METHOD Push(value)
NEW_NODE ← Node(value)
NEW_NODE.next ← top
top ← NEW_NODE
METHOD Pop()
IF top IS NULL
RETURN "Stack Underflow"
ELSE
value ← top.value
top ← top.next
RETURN value
METHOD Peek()
IF top IS NULL
RETURN "Stack is Empty"
ELSE
RETURN top.value
METHOD IsEmpty()
RETURN top IS NULL
Static Implementation Using an Array
A stack can also be implemented using a static array with a fixed size.
lightbulbExample
Example Pseudocode for Static Stack:
CLASS Stack
ARRAY data[size]
INTEGER top ← -1
METHOD Push(value)
IF top = size - 1
RETURN "Stack Overflow"
ELSE
top ← top + 1
data[top] ← value
METHOD Pop()
IF top = -1
RETURN "Stack Underflow"
ELSE
value ← data[top]
top ← top - 1
RETURN value
METHOD Peek()
IF top = -1
RETURN "Stack is Empty"
ELSE
RETURN data[top]
METHOD IsEmpty()
RETURN top = -1
METHOD IsFull()
RETURN top = size - 1
infoNote
Example Scenario
Browser History Navigation:
- Push: Each visited webpage is added to the stack.
- Pop: Moving back to the previous webpage removes the current page from the stack.
- Peek: Viewing the last visited page without leaving it.
Note Summary
infoNote
Common Mistakes
- Stack Overflow/Underflow:
- Overflow occurs when pushing onto a full stack (in static implementations).
- Underflow occurs when popping from an empty stack.
- Not Updating the Top Pointer Properly:
- Forgetting to adjust the
toppointer afterPushorPopcan lead to incorrect behaviour.
- Misunderstanding LIFO:
- Students sometimes confuse stacks with queues, which follow FIFO (First In, First Out).
infoNote
Key Takeaways
- Stacks follow the LIFO principle and are useful in scenarios like function call management, undo operations, and DFS.
- Key operations include Push, Pop, Peek, and IsEmpty.
- Stacks can be implemented dynamically using linked lists or statically using arrays.
- Understand potential issues such as overflow and underflow in stack operations.