Notes › DSA
Stack and Queue
Both store items in a fixed order and allow adding/removing only at the ends — that restriction is what makes them useful.
| Stack | Queue | |
|---|---|---|
| Order | LIFO — last in, first out | FIFO — first in, first out |
| Add | push (top) |
push / enqueue (back) |
| Remove | pop (top) |
pop / dequeue (front) |
| Real life | Pile of plates, undo button | Ticket line, printer queue |
| In code | Function calls, undo, DFS | BFS, task scheduling, buffers |
All main operations are O(1).
Stack in C++
#include <stack>
stack<int> st;
st.push(10);
st.push(20);
cout << st.top(); // 20
st.pop(); // removes 20
cout << st.size(); // 1
bool e = st.empty();
Queue and deque in C++
#include <queue>
#include <deque>
queue<int> q;
q.push(1); q.push(2);
cout << q.front() << q.back(); // 1 2
q.pop(); // removes 1
deque<int> dq; // double-ended: add/remove at both ends
dq.push_front(5); dq.push_back(6);
dq.pop_front(); dq.pop_back();
Implementing them yourself
- Stack with an array: keep an index
top; push →a[++top] = x, pop →top--. - Queue with an array: use a circular buffer —
frontandrearmove forward with% capacity, so freed space is reused. - Queue using two stacks: push into
in; when popping, ifoutis empty move everything fromintoout. Each element moves at most once → amortised O(1). - Stack using queues: after pushing
x, rotate the queue soxis at the front.
Pattern 1: matching brackets
Push opening brackets; on a closing bracket the top must be its match.
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if ((c == ')' && t != '(') || (c == ']' && t != '[') || (c == '}' && t != '{')) return false;
}
}
return st.empty();
}
Pattern 2: monotonic stack
Keep the stack increasing or decreasing. Each element is pushed and popped once, so the whole pass is O(n).
Next greater element — for each element, the first bigger element to its right:
vector<int> nextGreater(vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1);
stack<int> st; // indices, values decreasing
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i]; // a[i] is the next greater for the popped index
st.pop();
}
st.push(i);
}
return ans;
}
Used for: stock span, daily temperatures, largest rectangle in a histogram, trapping rain water.
Pattern 3: expression evaluation
- Postfix (Reverse Polish): push numbers; on an operator pop two, apply, push the result.
- Infix → postfix: operators go on a stack by precedence (Shunting-yard algorithm).
Pattern 4: queue for BFS and "level by level"
A queue processes things in the order they were discovered — the basis of BFS in trees and graphs, and of the sliding-window maximum (with a deque).
Pattern 5: min stack
Keep a second stack (or pairs value, currentMin) so getMin() is O(1).
Classic problems
| Problem | Structure |
|---|---|
| Valid parentheses | stack |
| Min stack | two stacks |
| Next greater element / daily temperatures | monotonic stack |
| Largest rectangle in histogram | monotonic stack |
| Evaluate reverse Polish notation | stack |
| Implement queue using stacks | two stacks |
| Sliding window maximum | monotonic deque |
| Rotting oranges / shortest path in grid | queue (BFS) |
Practise them in the Stack & Queue section.
Interview one-liners
- Recursion uses a stack — the call stack; deep recursion can cause stack overflow.
- Priority queue is not a normal queue — it removes the smallest/largest first (see Heaps).
- Deque supports both ends in O(1); Python's
collections.dequeand Java'sArrayDequeare the go-to choices. - Java: prefer
ArrayDequeover the oldStackclass.