Stack, Queue & Priority Queue
std::stack (LIFO), std::queue (FIFO), and std::priority_queue (always-sorted-by-priority) — and where each shows up in real code.
Container Adapters — Restricting Access on Purpose
stack, queue, and priority_queue are a bit different from the containers you've met so far. They're adapters — thin wrappers built on top of another container (a deque by default) that deliberately hide most of its interface, exposing only the handful of operations that make sense for a specific access pattern.
That restriction is a feature, not a limitation. If your algorithm only ever needs "look at the most recently added item," giving yourself access to the whole underlying container is just an invitation for bugs. These adapters make the correct usage pattern the only usage pattern.
std::stack — Last In, First Out
A stack<T> only lets you touch the top: .push() adds an element on top, .pop() removes the top element, and .top() peeks at it without removing it.
#include <iostream> #include <stack> using namespace std; int main() { stack<int> st; st.push(10); st.push(20); st.push(30); cout << "Top: " << st.top() << endl; // 30 st.pop(); // removes 30 cout << "Top after pop: " << st.top() << endl; // 20 cout << "Size: " << st.size() << endl; return 0; }
Real Use Case: Balanced Brackets
A classic stack application: checking whether every opening bracket in an expression has a matching, correctly-nested closing bracket. Every time you see an opener, push it. Every time you see a closer, the top of the stack MUST be its matching opener.
#include <iostream> #include <stack> #include <string> using namespace std; bool isBalanced(const string& expr) { stack<char> st; for (char c : expr) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else if (c == ')' || c == ']' || c == '}') { if (st.empty()) return false; char top = st.top(); st.pop(); if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) { return false; } } } return st.empty(); // true only if every opener was closed } int main() { cout << isBalanced("{[()]}") << endl; // 1 (true) cout << isBalanced("{[(])}") << endl; // 0 (false) return 0; }
If a closer ever finds the wrong opener on top — or finds an empty stack — the string is unbalanced immediately. At the very end, the stack must be completely empty; anything left over means an opener was never closed.
std::queue — First In, First Out
A queue<T> models a line of people: whoever joined first gets served first. .push() adds to the back, .pop() removes from the front, and .front() peeks at whoever is next.
#include <iostream> #include <queue> #include <string> using namespace std; int main() { queue<string> line; line.push("Alice"); line.push("Bob"); line.push("Charlie"); cout << "Front of line: " << line.front() << endl; // Alice line.pop(); // Alice leaves cout << "Next: " << line.front() << endl; // Bob return 0; }
Queues show up everywhere: task schedulers process jobs in arrival order, breadth-first search visits nodes level by level using a queue, and print spoolers process documents in the order they were submitted.
std::priority_queue — Always the Biggest First
A priority_queue<T> is a heap in disguise: .push() adds an element anywhere, but .top() always returns the largest element currently stored, and .pop() removes it. By default it's a max-heap.
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int> maxHeap; // max-heap by default maxHeap.push(30); maxHeap.push(10); maxHeap.push(50); cout << "Largest: " << maxHeap.top() << endl; // 50 maxHeap.pop(); cout << "Next largest: " << maxHeap.top() << endl; // 30 // Min-heap: pass a comparator as the third template argument priority_queue<int, vector<int>, greater<int>> minHeap; minHeap.push(30); minHeap.push(10); minHeap.push(50); cout << "Smallest: " << minHeap.top() << endl; // 10 return 0; }
priority_queue<int, vector<int>, greater<int>> means: store ints, back it with a vector<int> (the default underlying container anyway), and order elements using greater<int> instead of the default less<int> — which flips it into a min-heap.Lesson Summary
std::stack is LIFO — .push(), .pop(), .top(). Great for bracket matching and undo stacks.std::queue is FIFO — .push(), .pop(), .front(). Great for task/order processing.std::priority_queue always keeps the highest-priority element at .top() — max-heap by default.greater<T> as the comparator to turn a priority_queue into a min-heap.Now it's your turn to write real code. Complete the challenge below in any C++ compiler.
Write a program that:
1. Fills a
queue<int> with {1, 2, 3, 4, 5} (in that push order).2. Uses ONLY a
stack<int> as helper storage to reverse the order of the queue's elements.3. Prints the final queue — it should now read
5 4 3 2 1 when popped front-to-back.
Rules: You may only use stack/queue operations (
push, pop, front, top, empty) — no vectors or arrays as a shortcut.
💡 Show hints if you're stuck
- Step 1: pop every element out of the queue and push each one onto the stack — this alone reverses their order.
- Step 2: pop every element out of the stack and push each one back onto the queue.
- Think through why one pass through a stack reverses order, but two passes (queue→stack→queue) restores original order — you only want ONE reversal here.