Stacks
A stack is a fundamental abstract data structure that operates on a LIFO principle.
LIFO
Last-in, First-out principle.
This means that the last element added to the stack is the first one to be removed.
- A stack is like a stack of plates.
- You can only add or remove the top plate, which makes it easy to manage but limits access to other plates.
Key Characteristics of a Stack
- LIFO Order: Elements are added and removed from the top of the stack.
- Limited access: Only the top element is accessible at any given time.
- Dynamic size: Stacks can grow or shrink depending on the implementation (linked list) or have a fixed size (array).
Core Operations of a Stack
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element of the stack.
- Peek (or Top): Returns the top element without removing it.
- isEmpty: Checks if the stack is empty, returning true or false..
In IB's official pseudocode, stacks have methods:
- push()
- pop()
- isEmpty()
Recursive functions use the call stack, a special stack in memory, to keep track of function calls and their local variables:
- Stacks are used to store return addresses when a function is called.
- This ensures that the program can return to the correct location after the function completes.
- When a function is called, its return address and local variables are pushed onto the stack.
- When the function returns, these are popped off, restoring the previous state.
You can experiment with call stacks on websites like pythontutor.com.
- Stacks are used in applications like text editors to implement undo functionality.
- Each action is pushed onto a stack, and undoing an action involves popping it off and reversing it.
- In web browsers, the back button uses a stack to store previously visited pages, allowing you to navigate backwards.
Constructing Algorithms Using Stack Access Methods
Usually, there are 3 general steps you need to take care of:
- Initialise the Stack: Create an empty stack.
- Process Data: Use push to add elements and pop to remove them as needed.
- Check Conditions: Use isEmpty to determine if the stack has more elements to process.
Always check if the stack is empty before calling pop to avoid errors.
- Use stacks for reversal: Stacks naturally reverse the order of elements, making them ideal for tasks like reversing strings or lists.
- Think LIFO: When designing algorithms, consider if a LIFO approach is suitable for the problem.
Reversing a String
Let's construct an algorithm to reverse a string using a stack.
- Initialise the Stack: Create an empty stack.
- Push Characters: Loop through the string and push each character onto the stack.
- Pop Characters: Pop each character from the stack and append it to a new string.
// Given string to reverse STR with length N characters
// Given an empty stack STACK
loop I from 0 to N-1
STACK.push(STR.charAT(I)) // Add character on Ith position to stack
end loop
RESULT = ""
loop while NOT STACK.isEmpty()
LETTER = STACK.pop() // get letter from top of the stack
RESULT = RESULT + LETTER
end loop
output RESULTIf the input is"hello", the stack will store['h', 'e', 'l', 'l', 'o'].
Balancing Parentheses
Stacks are ideal for checking if parentheses in an expression are balanced.
- Initialise the Stack: Create an empty stack.
- Process Each Character:
- When encountering (, push element to the stack.
- Pop the stack when encountering ).
- Check Balance: If the stack is empty at the end, the parentheses are balanced.
Expression calculation
Stacks are essential in evaluating mathematical expressions, particularly those in postfix (Reverse Polish Notation) or prefix notation.
Infix
- The operator is between the operands.
- Requires operator precedence rules or conversion to postfix/prefix for stack-based evaluation.
Infix expressions can be converted to postfix using the shunting-yard algorithm, which also relies on stacks.
3 + 4 * 2
Postfix (Reverse Polish Notation)
Operator comes after operands.
3 4 + 2 *
Evaluation using stack:
- Push 3 and 4 onto the stack.
- Pop 4 and 3, add them => push 7.
- Push 2, pop 2 and 7, multiply => push 14.
- Stack now contains result 14.
Prefix (Polish Notation)
Operator comes before operands.
* + 3 4 2
Evaluation using stack (process from right to left):
- Push operands onto the stack as you read.
- When encountering an operator, pop required operands, perform the operation, and push the result.
- Stack eventually contains the final result.
- What are the key characteristics of a stack?
- How do stacks support recursive processes?
- Can you think of other real-world scenarios where stacks might be helpful?
What other real-world systems rely on LIFO principle?
