Stack
Overview
A Stack is an abstract data type (ADT) that follows the Last In, First Out (LIFO) principle. The most recently added element is the first one to be removed.
Stacks model nested and reversible processes.
What Is a Stack?
A stack:
- Allows access from only one end
- Has a top element
- Restricts operations to push and pop
You cannot directly access elements in the middle.
Core Stack Operations
| Operation | Description |
|---|---|
| Push | Add an element to the top |
| Pop | Remove the top element |
| Peek / Top | View the top element |
| IsEmpty | Check if stack is empty |
| Size | Number of elements |
How It Works
Stacks are commonly implemented using:
- Arrays
- Linked lists
The ADT defines behavior, not storage.
Example
Pseudocode
stack.push(10)
stack.push(20)
stack.pop() // 20
stack.peek() // 10
Real-world Analogy
A stack is like a pile of plates. You always take the top one first 🍽️.
Time Complexity
| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
Use Cases
- Function call management
- Undo / redo operations
- Expression evaluation
- Syntax parsing
- Backtracking algorithms
Advantages
- Simple and fast
- Predictable behavior
- Useful for recursion
Limitations
- Restricted access
- No random element retrieval
- Stack overflow risk