Stacks follow the Last-In First-Out (LIFO) principle, which influences the time taken to perform operations like push, pop, and peek. In this guide, we’ll explore the time complexities of five core stack operations.
Summary Table
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Push | O(1) | O(1) | O(1) |
| Pop | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) |
| isEmpty | O(1) | O(1) | O(1) |
| Traversal | O(N) | O(N) | O(N) |
1. Push
Push adds a new element to the top of the stack.
- Best Case – O(1): The element is added directly to the top of the stack. No shifting or resizing is needed.
- Average Case – O(1): Most stack implementations are dynamic and grow as needed, so push remains constant time.
- Worst Case – O(1): Even when resizing is needed (in dynamic stacks), amortized analysis still results in O(1) per push.
2. Pop
Pop removes the top element from the stack.
- Best Case – O(1): The top element is removed directly without needing to access or modify other elements.
- Average Case – O(1): Since access is always at the top, it’s a constant-time operation regardless of stack size.
- Worst Case – O(1): There is no worst-case delay in popping; it’s always O(1).
3. Peek
Peek returns the top element without removing it.
- Best Case – O(1): The top element is accessed directly.
- Average Case – O(1): Access is constant in all typical stack implementations.
- Worst Case – O(1): Always O(1) since it only reads the top element.
4. isEmpty
isEmpty checks whether the stack contains any elements.
- Best Case – O(1): Usually implemented by checking a pointer or length variable.
- Average Case – O(1): Constant time across all cases as it doesn’t depend on stack size.
- Worst Case – O(1): Always constant-time.
5. Traversal
Traversal involves visiting every element from top to bottom of the stack.
- Best Case – O(N): Every element must be visited, so the time complexity depends on the number of elements.
- Average Case – O(N): On average, traversal takes linear time as all elements are visited once.
- Worst Case – O(N): Worst case is also O(N), as all elements are accessed sequentially.