Stacks (OCR A-Level Computer Science): Revision Notes
📚Revision Notes
Stacks
Overview
A stack is a linear data structure that stores data in a Last-In, First-Out (LIFO) order. This means that the last item added to the stack is the first one to be removed. Stacks are widely used in various scenarios, such as managing function calls, evaluating expressions, and undoing operations in software applications. Understanding stacks and how to implement them is crucial for problem-solving and algorithm development.
Structure of a Stack
A stack supports two primary operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the element from the top of the stack. Other useful operations include:
- Peek: Retrieves the top element without removing it.
- isEmpty: Checks if the stack is empty.
- isFull (optional in fixed-size implementations): Checks if the stack has reached its capacity.
Implementing a Stack
Using Arrays (Procedural Approach)
Push Operation:
- Check if the stack is full (optional for dynamic arrays).
- Increment the top pointer.
- Add the new element at the top index.
Pop Operation:
- Check if the stack is empty.
- Retrieve the element at the top index.
- Decrement the top pointer.
Note
Pseudocode Example
# Stack using a fixed-size array
MAX_SIZE = 10
stack = [None] * MAX_SIZE
top = -1 # Initialise stack as empty
def push(element):
global top
if top == MAX_SIZE - 1:
print("Stack Overflow")
return
top += 1
stack[top] = element
def pop():
global top
if top == -1:
print("Stack Underflow")
return None
element = stack[top]
top -= 1
return element
Using a Linked List (Alternative Data Structure)
A stack can also be implemented using a linked list, where each node contains the data and a reference to the next node.
Push: Create a new node and link it as the new top.
Pop: Remove the top node and update the top pointer.
Using Object-Oriented Programming (OOP)
In OOP, stacks are typically implemented as classes.
Example
Example in Python:
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
return "Stack Underflow"
return self.items.pop()
def peek(self):
if self.is_empty():
return None
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
Examples
Note
Using a Stack to Reverse a String:
def reverse_string(s):
stack = Stack()
for char in s:
stack.push(char)
reversed_str = ''
while not stack.is_empty():
reversed_str += stack.pop()
return reversed_str
Note
Checking for Balanced Parentheses:
def is_balanced(expression):
stack = Stack()
for char in expression:
if char in "({[":
stack.push(char)
elif char in ")}]":
if stack.is_empty():
return False
top = stack.pop()
if not matches(top, char):
return False
return stack.is_empty()
def matches(opening, closing):
pairs = {'(': ')', '{': '}', '[': ']'}
return pairs[opening] == closing
Note Summary
Note
Common Mistakes
- Not Checking for Underflow/Overflow:
- Forgetting to check if the stack is empty before popping or peeking can cause errors.
- In fixed-size implementations, failing to handle overflow when pushing can lead to out-of-bounds errors.
- Confusing LIFO with FIFO:
- Stacks follow a Last-In, First-Out order, not First-In, First-Out (FIFO). Ensure you're using the correct structure for the problem.
- Off-by-One Errors:
- Incorrectly initialisng or updating the top pointer can lead to missing elements or accessing invalid indices.
Note
Key Takeaways
- A stack is a LIFO data structure with primary operations: push, pop, and peek.
- Stacks can be implemented using arrays, linked lists, or as objects in OOP.
- Understanding stack operations and common implementation patterns is more important than memorising code.
- Practice reading, tracing, and writing stack-related code to strengthen your problem-solving skills.