Stack
A linear data structure that follows the LIFO (Last In, First Out) principle.
Intuition
Think of a stack of plates in a cafeteria. You can only add a new plate to the top (Push) and remove the top plate (Pop). The last plate added is the first one to be removed. This is known as LIFO (Last In, First Out).
Concept
A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).
How it Works
We maintain a pointer (often called 'top') that tracks the last element added.
- Push: Increment top index, add element at top.
- Pop: Return element at top, decrement top index.
- Peek: Return element at top without changing top index.
Step-by-Step Breakdown
- Start Empty: Stack is empty, top is -1.
- Push(10): Top becomes 0, Stack[0] = 10.
- Push(20): Top becomes 1, Stack[1] = 20.
- Pop(): Return Stack[1] (20), Top becomes 0.
Example Trace
Push(5)
5 is added to the empty stack.
[5]
Push(8)
8 is placed on top of 5.
[5, 8]
Pop()
Remove the top element (8). 5 becomes new top.
[5]
When to Use
- LIFO Processing: When you need to access the most recently added element first (e.g., Undo).
- Backtracking: Storing previous states to return to them (e.g., Maze solving).
- Parsing: Syntax checking (parentheses) and expression evaluation.
When NOT to Use
- Random Access: Accessing the
k-thelement is O(n), unlike Arrays O(1). - Searching: Finding an item requires popping elements off, destroying the stack order.
How to Identify
Look for problems involving nested structures (like parentheses), reversing sequences, or finding the "nearest" element with a certain property. Keywords: "Last In First Out", "Undo/Redo", "Back/Forward", "Parentheses".
Frequently Asked Questions
What is LIFO in a Stack?
LIFO stands for Last-In-First-Out, meaning the last element added to the stack is the first one to be removed.
What is Stack Overflow vs Stack Underflow?
Stack Overflow occurs when you try to push an element onto a full stack. Stack Underflow occurs when you try to pop an element from an empty stack.
Real-world examples of a Stack?
Stacks are used in browser history (back button), undo/redo functionality in editors, and function call management in programming languages.