Understanding Stacks as LIFO Data Structures
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
- The last item added is the first one removed.
- Analogy: Like a stack of plates in a cafeteria—you can only add/remove the plate at the top.
Hint
Always think “last added = first out.”
Common Mistake
Assuming you can directly access elements in the middle (not possible without popping).
Fundamental Stack Operations
- Push
- Adds an item to the top of the stack.
- Time Complexity: O(1)
- Pop
- Removes and returns the item from the top.
- Time Complexity: O(1)
- Peek / Top
- Returns the top element without removing it.
- Time Complexity: O(1)
- isEmpty
- Checks whether the stack is empty.
- Time Complexity: O(1)
Hint
Push/Pop/Peek always work at the top only.
Common Mistake
Forgetting to check isEmpty before pop() → runtime error.
Performance and Memory Considerations
- Performance
- push() and pop() are very efficient (O(1)).
- Accessing anything other than the top requires removing items (O(n)).
- Memory Usage
- Static Stacks: Fixed size (array-based). Can waste memory if underused or overflow if exceeded.
- Dynamic Stacks: Grow/shrink automatically (linked-list or dynamic array). Flexible but incur resizing overhead.
Common Applications of Stacks
- Recursive Problems
- Call stacks manage function calls and return addresses in recursion.
- Parsing & Syntax Checking
- Matching brackets {}, [], () in compilers or calculators.
- Undo / Redo Functions
- Store history of user actions for rollback.
- Reversing Data
- Push elements then pop them to reverse order.
Hint
In exams, mention stacks in parsing (compilers) or undo features (text editors).
Common Mistake
Mixing up stack use with queues (stack = LIFO, queue = FIFO).
Exam technique
If asked to explain or trace a stack:
- Always draw it vertically (top at the top).
- Show push/pop step by step.
- Mention O(1) efficiency for basic operations.
