Stacks and Queues
On this page
Some problems are about order: the most recent thing you opened must be the first one you close, or the first thing you discovered must be the first one you process. Trying to track that with indexes into an array gets messy fast. Stacks and queues are arrays (or lists) with a rule about which end you use, and that rule is often the whole solution.
How it works

Stack: last in, first out
A stack only touches one end, the top. push puts an item on top, pop removes the top item, peek looks at it without removing it. The item you take out is always the one you put in most recently.
Every language gives you one for free: a Python list (append and pop), Java ArrayDeque (push, pop, peek), C++ std::stack or vector, and a Go slice (append, then s = s[:len(s)-1]).
Queue: first in, first out
A queue adds at the back and removes from the front, like a line at a shop. In Python use collections.deque (append, popleft); in Java ArrayDeque (offer, poll); in C++ std::queue; in Go a slice with a moving head index, or container/list.
A deque (double-ended queue) allows both ends, and can act as either.
Why they appear in so many problems
- A stack remembers what is still open: brackets, function calls, unfinished tags, numbers waiting for an operator. When you meet a closer, the matching opener is always on top.
- A queue remembers what is waiting, in discovery order. That is exactly what breadth-first search needs.

Operations and costs
| Operation | Stack | Queue (deque) |
|---|---|---|
| Add | push: O(1) | enqueue at back: O(1) |
| Remove | pop top: O(1) | dequeue front: O(1) |
| Look at next item | peek: O(1) | front: O(1) |
| Search for a value | O(n) | O(n) |
The one trap: a plain Python list used as a queue with pop(0) is O(n), because every element shifts. Always use deque.
When to reach for it
Use a stack when:
- Things must be closed in the reverse order they were opened: bracket matching, HTML tags, undo history.
- You need to evaluate expressions: postfix notation, or a calculator with
+ - * /. - You need the next greater or smaller element: a monotonic stack keeps elements in sorted order and pops everything the new element beats. Each element is pushed and popped once, so it's O(n) overall.
- You want to turn recursion into a loop (iterative DFS).
Use a queue when:
- You explore level by level: breadth-first search on a tree, a grid or a graph, and shortest paths when every step costs the same.
- You process tasks in arrival order, or keep a sliding window of recent items.

Example
Check whether a string of brackets is valid: every opener is closed by the same type, in the right order.
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in pairs: # a closer
if not stack or stack[-1] != pairs[c]:
return False
stack.pop()
else: # an opener
stack.append(c)
return not stack # nothing left open
boolean isValid(String s) {
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (pairs.containsKey(c)) {
if (stack.isEmpty() || !stack.peek().equals(pairs.get(c))) return false;
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
bool isValid(const string& s) {
unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
stack<char> st;
for (char c : s) {
if (pairs.count(c)) {
if (st.empty() || st.top() != pairs[c]) return false;
st.pop();
} else {
st.push(c);
}
}
return st.empty();
}
func isValid(s string) bool {
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
stack := []rune{}
for _, c := range s {
if open, ok := pairs[c]; ok {
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, c)
}
}
return len(stack) == 0
}
Time: O(n). Space: O(n) in the worst case (all openers).
Three tests cover the logic: "([]{})" is valid, "([)]" fails at the mismatch, and "((" fails at the end because the stack isn't empty.
Common mistakes
- Popping an empty stack. Check for empty before
poporpeek; a lone")"should return false, not crash. - Forgetting the final check. A string of only openers passes the loop; the answer depends on the stack being empty at the end.
- Using a list as a queue.
list.pop(0)in Python is O(n). Usedeque.popleft(). - Java's
Stackclass. It works but is old and synchronized;ArrayDequeis the usual choice. Compare boxedCharactervalues withequalsif you store them in collections and compare two objects. - Pushing values when you need positions. For problems like Daily Temperatures you need the index on the stack, not the value, to compute distances.
Say this in the interview
- "The most recently opened bracket has to close first, which is last in, first out, so I'll use a stack."
- "Each element is pushed and popped at most once, so even with the inner while loop the total is O(n)."
- "I'll use a deque for the BFS queue so dequeuing is O(1)."
Used in
- Patterns: Stacks and Monotonic Stacks, Tree BFS, Graph BFS and DFS
- Problems: Valid Parentheses, Min Stack, Daily Temperatures, Basic Calculator II, Sliding Window Maximum (deque), Rotting Oranges (queue)
- Data structures: Arrays and Strings, Linked Lists