Stack
A linear data structure that follows the LIFO (Last-In, First-Out) principle, where insertion and deletion happen only from the top.
Fundamental Concepts
LIFO Principle (Last-In, First-Out)
Push (Add to top)
Pop (Remove from top)
LIFO (Last-In, First-Out) means the last element added to a collection is the first element to be removed.
Push
10
20
Push adds an element to the top of the stack, with O(1) time complexity.
Pop
10
20
30
Pop removes the top element from the stack, with O(1) time complexity.
Peek
10
20
30
40
Peek returns the top element without removing it, with O(1) time complexity.
Search
10
20
30
40
Search must check each element from the top, resulting in O(n) time complexity.
Traversal
10
20
30
40
Traversal requires visiting all elements, usually from top to bottom, resulting in O(n) time complexity.
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Push | O(1) | Add element to the top |
| Pop | O(1) | Remove element from the top |
| Peek | O(1) | View top element without removal |
| Search | O(n) | Requires scanning from the top |
| Traversal | O(n) | Requires visiting all elements |
When to Use Stacks
- Managing function calls in recursion (the "call stack").
- Implementing Undo/Redo functionality in applications.
- Parsing expressions (e.g., checking for balanced parentheses).
- Backtracking algorithms, like navigating a maze, where you need to reverse steps.