Definition
Stack is a Last In First Out (LIFO) data structure. Like a stack of plates, the last item added is the first one to be removed.
Key Characteristics
- ✓LIFO (Last In, First Out) - Last added item comes out first
- ✓Push and pop operations have O(1) time complexity
- ✓Top pointer to check the topmost element
- ✓Frequently used in recursion and undo operations
Use Cases
Used in these scenarios:
Browser Back Button
Visited pages are stored in a stack, and pressing the back button retrieves the most recent page.
Undo (Ctrl+Z)
Document editors save actions in a stack, and undo operations revert the most recent action.
Parenthesis Matching
When checking if parentheses are properly closed, opening brackets are pushed onto the stack and matched with closing brackets.
Recursion to Iteration
When converting recursive functions to iterative ones, function call states are stored in a stack to mimic recursion.
Operations
Main operations:
push
O(1)Add an element to the top of the stack.
pop
O(1)Remove and return the top element from the stack.
peek / top
O(1)View the top element without removing it.
isEmpty
O(1)Check if the stack is empty.
Complexity
Time Complexity
Space Complexity
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization