Stacks
A stack is a fundamental abstract data structure that operates on a LIFO principle.
Definition
LIFO
Last-in, First-out principle.
This means that the last element added to the stack is the first one to be removed.
Analogy- 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.
Example- 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.
Tip- 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.
