Understanding how stacks work and why push operations are constant time
A stack is a data structure that follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates or books - you can only add or remove items from the top!
Key Operations:
Stacks are implemented using arrays (or linked lists), and since push and pop operations only work at one end (the top), they are extremely efficient - O(1) constant time!
When you push an element, it's added to the end of the array. Since arrays support O(1) insertion at the end, push is O(1).
Unlike inserting at the beginning of an array (which requires shifting all elements), pushing to the end doesn't require any element movement.
Push is essentially just:
stack[stack.length] = newElement; // O(1)
stack.push(newElement); // O(1)Code Example:
// Creating and using a stack
const stack = [];
// O(1) - Push operation
stack.push(10); // [10]
stack.push(20); // [10, 20]
stack.push(30); // [10, 20, 30]
// O(1) - Pop operation
const top = stack.pop(); // Returns 30, stack: [10, 20]Adding an element to the end of an array is O(1) because you know exactly where the end is (array.length), and you don't need to move any existing elements.
Unlike inserting at the beginning or middle of an array (which requires shifting all subsequent elements), pushing to the end requires no shifting at all.
Push is a single, atomic operation:
stack[stack.length] = value; // One assignment
// or stack.push(value) - same thing!When an array needs to grow beyond its capacity, it may need to be resized (allocate new memory and copy elements). However, this happens infrequently and is amortized O(1) - meaning the average cost per push operation is still O(1).
| Operation | Stack | Array (Beginning) | Explanation |
|---|---|---|---|
| Push (Add to End) | O(1) | O(1) | Both are O(1) - adding to the end requires no shifting |
| Pop (Remove from End) | O(1) | O(1) | Both are O(1) - removing from the end requires no shifting |
| Insert at Beginning | N/A | O(n) | Arrays require shifting all elements - stacks don't support this |
| Access by Index | N/A | O(1) | Arrays support random access - stacks only allow top access |
When you click "Back" in your browser, it pops from a stack of visited pages. The most recent page (last in) is the first one you go back to (first out)!
Stacks are used to evaluate mathematical expressions and convert between infix, prefix, and postfix notation. Each operator and operand is pushed/popped as needed.
Text editors use stacks to implement undo. Each action is pushed onto a stack, and undo pops the most recent action. Redo uses another stack!
When functions call other functions, the computer uses a call stack. Each function call is pushed, and when it returns, it's popped. This is why recursion works!
Games use stacks to manage game states (menu, gameplay, pause, etc.). Pushing a new state pauses the current one, and popping returns to the previous state.
Both operations work at one end only, requiring no element shifting
Last In, First Out - the most recently added element is the first one removed
Stacks are ideal for problems involving reversal, matching parentheses, and backtracking
Despite its simplicity, stacks are fundamental to many algorithms and system operations