Stack Operations Explained
Every stack is defined by a small set of core operations. Understanding them is the first step to using stacks effectively in any program.
What is a Stack?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of it like a stack of plates in a cafeteria: you always add a plate to the top and remove the topmost plate first.
Every stack, regardless of its underlying implementation, supports a common set of operations. These operations all interact with only one end of the structure, which is called the top.
The Push Operation
Push adds a new element to the top of the stack. This is the only way to insert data into a stack. After a push, the new element becomes the top.
- Check if the stack has room (relevant for fixed-size arrays).
- Place the new element at position
top + 1. - Update the top pointer to point to the new element.
- The stack now has one more element.
Time complexity: O(1) - constant time, regardless of stack size.
Before Push(42)
After Push(42)
The Pop Operation
Pop removes the element at the top of the stack and returns it. After a pop, the element below it becomes the new top. Pop is the only way to remove data from a stack.
- Check if the stack is empty. If it is, handle the underflow.
- Read the element at position
top. - Update the top pointer to
top - 1. - Return the removed element.
Time complexity: O(1) - constant time.
Before Pop()
After Pop() returns 30
The Peek Operation
Peek (also called top or peek) returns the element at the top of the stack without removing it. This lets you inspect the most recently added element without changing the stack.
Peek is useful when you need to make a decision based on the current top value before deciding whether to pop or push. For example, in expression evaluation, you peek at the operator stack to check precedence before pushing a new operator.
- Check if the stack is empty. If it is, there is nothing to peek.
- Return the element at position
topwithout moving the pointer.
Time complexity: O(1) - constant time. No element is moved or removed.
isEmpty and Size
Two utility operations help you query the state of a stack:
isEmpty
Returns true if the stack contains zero elements, false otherwise. Use this before pop or peek to prevent underflow errors. In an array-based stack, isEmpty checks if top == -1. In a linked list stack, it checks if the head pointer is null.
Time: O(1)
size
Returns the number of elements currently in the stack. Some implementations track this with a counter variable that increments on push and decrements on pop. Others compute it from the top index. Both approaches are O(1).
Time: O(1)
Clearing a Stack
The clear (or reset) operation removes all elements from the stack, returning it to an empty state. This is faster than popping every element individually because it can reset internal state in one step.
In an array-based stack, clear simply sets top = -1. In a linked list stack, clear traverses and frees each node. Some languages provide a built-in clear method. Others require you to pop in a loop until isEmpty returns true.
When to Use Each Operation
Choosing the right operation depends on what you need to accomplish. Here are common scenarios:
Adding data
Use push when you receive new data that should be processed in reverse order later. Examples: undo systems, expression parsing, DFS traversal.
Removing the latest
Use pop when you need to process the most recently added item first. Examples: balanced parentheses checking, backtracking, function return.
Checking without removing
Use peek when you need to look ahead before deciding. Examples: operator precedence, next greater element, sliding window problems.
Safety checks
Use isEmpty before pop or peek to prevent runtime errors. Use size when you need to know how many elements remain for conditional logic.
Complete Operation Summary
| Operation | Time | Space | Description |
|---|---|---|---|
push(x) |
O(1) | O(1) | Add element x to the top of the stack |
pop() |
O(1) | O(1) | Remove and return the top element from the stack |
peek() |
O(1) | O(1) | Return the top element without removing it |
isEmpty() |
O(1) | O(1) | Return true if the stack has no elements |
size() |
O(1) | O(1) | Return the number of elements in the stack |
clear() |
O(1)* | O(1) | Remove all elements and reset the stack |
* O(1) for array-based stacks with a top pointer. O(n) for linked list stacks where each node must be freed.
Frequently Asked Questions
What is the difference between push and pop?
Push adds an element to the top of the stack. Pop removes the element at the top of the stack. Both operations only affect the top element and run in O(1) time.
What happens if you pop from an empty stack?
Popping from an empty stack causes a stack underflow error. In most languages this either throws an exception or returns a special value like null or undefined. Always check isEmpty before popping.
Is peek the same as pop?
No. Peek returns the top element without removing it from the stack. Pop removes the top element. Use peek when you need to inspect the top value without modifying the stack.
Why are stack operations O(1)?
Stack operations only modify or read one end of the data structure (the top). There is no need to shift elements or search through the structure, so each operation takes constant time regardless of stack size.
What does the clear operation do?
The clear operation removes all elements from the stack, resetting it to an empty state. In array-based implementations this means resetting the top pointer to -1. In linked list implementations you free each node.