Stacks, Queues, and Deques
Stacks and queues restrict where items enter and leave. Those restrictions turn execution order into a useful invariant: newest-first for stacks, oldest-first for queues, and both ends for deques.
LIFO: the stack
Push adds to the top, pop removes from the top, and peek observes it. Function call frames use a stack, as do expression parsing, bracket matching, undo histories, and depth-first search.
A stack is especially useful when the newest unresolved item must meet the next event. The top summarizes the only candidate that can be resolved now.
- Push, pop, and peek are normally O(1)
- An array-backed stack is compact
- An explicit stack can replace recursion
FIFO: the queue
Enqueue adds at the rear and dequeue removes from the front. Breadth-first search uses a queue so vertices are processed in nondecreasing distance from the source in an unweighted graph.
Do not implement a queue by repeatedly removing index zero from a dynamic array if that shifts every element. Use a deque, linked queue, circular buffer, or a head index.
- Scheduling and buffering
- Breadth-first traversal
- Producer-consumer pipelines
Terms, operations, and practical uses
Ordering rules
- StackLast in, first out: the newest unresolved item is processed first.
- QueueFirst in, first out: items are processed in arrival order.
- DequeInsertion and removal are available at both the front and rear.
Basic operations
- Push / popAdd to or remove from the top of a stack.
- Enqueue / dequeueAdd at the rear or remove from the front of a queue.
- PeekRead the next removable item without changing the structure.
Where they appear
- Call stackRemembers suspended function calls and their local state.
- Breadth-first searchUses a queue so vertices are expanded by increasing edge distance.
- Monotonic dequeKeeps only candidates that can still become a window minimum or maximum.
Check whether brackets are balanced
def balanced(text):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for char in text:
if char in "([{":
stack.append(char)
elif char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
return not stack
print("Balanced" if balanced("{[()]}") else "Not balanced")bool balanced(const string& text) {
unordered_map<char, char> pair = {
{')', '('}, {']', '['}, {'}', '{'}
};
stack<char> opened;
for (char ch : text) {
if (ch == '(' || ch == '[' || ch == '{') opened.push(ch);
else if (pair.count(ch)) {
if (opened.empty() || opened.top() != pair[ch]) return false;
opened.pop();
}
}
return opened.empty();
}static boolean balanced(String text) {
Map<Character, Character> pair = Map.of(
')', '(', ']', '[', '}', '{'
);
Deque<Character> opened = new ArrayDeque<>();
for (char ch : text.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') opened.push(ch);
else if (pair.containsKey(ch)) {
if (opened.isEmpty() || opened.pop() != pair.get(ch)) return false;
}
}
return opened.isEmpty();
}{[()]}BalancedRun the example step by step
Deques and circular buffers
A deque supports insertion and removal at both ends. A circular buffer maps logical positions around a fixed array with modular arithmetic, reusing freed slots instead of shifting data.
Track head, tail, size, and capacity with one consistent convention. Many bugs come from mixing whether tail means the last element or the next free slot.
- Both-end operations are O(1)
- Bounded buffers can reject or overwrite when full
- One empty slot can distinguish full from empty, or size can be stored explicitly
Monotonic structures
A monotonic stack keeps values increasing or decreasing so the next greater or smaller boundary becomes available when an item is popped. A monotonic deque additionally removes expired indices from the front, enabling linear-time sliding-window extrema.
Although an iteration may pop several items, each item enters and leaves once. That is the amortized argument for O(n) total work.
- Next greater element
- Histogram boundaries
- Sliding-window maximum
- Remove dominated candidates immediately