stack, queue and priority_queue

Why this matters

Many programs have to hold items that are waiting for their turn. A web browser remembers the pages you visited so the back button works. A printer keeps a line of documents. A hospital ranks patients by how urgent their case is. Interview problems use the same ideas. Checking that brackets match, finding the shortest route through a maze and picking the ten biggest numbers from a stream all reduce to choosing the right waiting line.

The STL gives you three containers for these jobs: stack, queue and priority_queue. Each one is small on purpose. It offers only the few moves its job needs, and it hides the rest. That limit is useful, because a stack that cannot be indexed cannot be misused as a random list. This lesson covers each container, shows it working on a real task, and explains how to choose between them.

Three rules for a waiting line

Before any code, picture three everyday waiting lines.

A stack is a pile of plates in a kitchen. You put a clean plate on the top, and when you need one, you take the top plate. The plate you put on last comes off first. Computer scientists call this last in, first out, abbreviated LIFO.

A queue is a line at a ticket counter. The person who arrived first is served first. New people join at the back, and service happens at the front. This is first in, first out, abbreviated FIFO.

A priority queue is the waiting room of a hospital emergency department. Arrival order does not decide who is seen next. The most urgent case is seen next, whenever it arrived. The container always gives you the item that ranks highest under a rule you choose.

Each of these three rules answers a different question. A stack answers "what did I do most recently?", a queue answers "what has waited longest?" and a priority queue answers "what matters most right now?" If you can say which question your problem asks, you have most of the answer.

stack: last in, first out

A stack holds items in a pile. It has four operations you will use all the time.

• push(x) puts x on the top. It is O(1).
• top() returns the value on the top without removing it. It is O(1).
• pop() removes the top value. It is O(1). It returns nothing, so read the value with top() first.
• empty() and size() tell you how many items are there. They are O(1).

The diagram below shows a stack and a queue side by side, with the place where items are added and removed marked on each. Both containers give constant-time adds and removes at their working ends. Only the order they release items differs.

A stack adds and removes at the top, while a queue adds at the back and removes at the front

The stack is a natural fit for any problem where the most recent thing matters most. The clearest examples are the undo button in an editor, the call stack that tracks which function is running, and the matching of brackets. The next section shows that last example in full. After that, you will see the stack at work in an undo program, which models the editor's undo button.

The stack container is an adaptor. An adaptor is a container built on top of another container, which it uses for storage. By default a stack stores its items in a deque. It offers only the stack moves and hides the others. You cannot write s[2] on a stack, and you cannot loop over it with a range-based for. To see every item you pop them one at a time, which empties the stack.

Step through the animation above to see the pushes and pops. Pay attention to what the top value is after each step. In most stack bugs, the program reads the top after a pop or before a push, when the value it expects is no longer there.

Worked example 1: matching brackets

A compiler reads (a[1] + {2}) and must decide whether the brackets match. The idea is simple once you see it. Each opening bracket waits on the stack. Each closing bracket must match the bracket on the top, because that is the most recent opening bracket still waiting. When the walk finishes, the stack must be empty, or some opening bracket never closed.

This program reads a count and then that many strings, and prints YES or NO for each one. Type this into the Input box:

5
{[()]}
([)]
((
[]{}
)(

The output is:

YES
NO
NO
YES
NO

Trace the second line, ([)]. The ( is pushed, then the [ is pushed, so the stack holds ( [ with the [ on top. The next character is ). It must match the top, but the top is [, so the function returns false. Output NO. The brackets are in the wrong nesting order.

Now trace )(. The first character is ), and the stack is empty. There is nothing to match, so the answer is NO immediately. The last line, )(, shows why the empty check comes before the top() call.

The line return st.empty(); covers the case where brackets are opened and never closed. The input (( pushes two items and then ends. The stack still holds them, so the answer is NO. The code reads s with cin >> s, which stops at a space. The input has no spaces, so this works.

Worked example 2: an undo history

An editor keeps a stack of past states. Each change pushes the old text. Undo pops the most recent state and restores it. This program models that behaviour with words. A type command adds a word, and an undo command reverses the last change. It prints the document after each command.

Type this into the Input box:

type hello
type world
undo
undo
undo
type again

The output is:

[hello]
[hello world]
[hello]
[]
nothing to undo
[again]

Each type saves the old document before it changes it. That is the key idea. The stack holds a snapshot of every earlier state, with the most recent on top. An undo copies the top snapshot back and removes it. After the first two lines, the stack holds two snapshots: the empty document and hello. The first undo restores hello. The second restores the empty document. The third undo finds the stack empty, so there is nothing left to restore.

Notice the continue in the empty case. It skips the line that prints the document, so the program prints only the message. Without it, the program would print the document after a failed undo, which is a small but confusing difference.

Worked example 3: reverse Polish notation

Calculators and some compilers write arithmetic in an order that makes the stack almost obvious. This order is called reverse Polish notation, often shortened to RPN. In RPN, each operator comes after its two operands. The expression 3 4 + means 3 plus 4. To evaluate it, you push numbers and apply operators to the top two numbers.

This program reads one RPN expression per line and prints the value of each. Type this into the Input box:

3 4 + 2 * 7 -
10 2 8 * + 3 -
100 7 /

The output is:

7
23
14

The first line is 3 4 + 2 * 7 -. Push 3, then push 4. The + pops 4 and 3, adds them, and pushes 7. Push 2. The * pops 2 and 7, multiplies to 14, and pushes 14. Push 7. The - pops 7 and 14. It computes the first minus the second, which is 14 minus 7, so the stack holds 7. The output is 7.

Order matters for - and /. The code pops b first and a second, so a is the value that was pushed earlier. Subtraction is therefore a - b. If you swapped the names, 10 2 - would give -8 instead of 8. The third line uses integer division, so 100 7 / is 14 and not 14.28.

The function calls stoi, which turns a string into an int, and it is the reason the number branch works. Real calculators also check for an operator with too few numbers on the stack. This program does not, so a line such as + alone would call top() on an empty stack. Adding that check is the first practice question below.

Worked example: the next greater value

A common interview question asks, for every number in a list, for the first number to its right that is larger. If no larger number exists, the answer is -1. The obvious solution looks to the right from each position until it finds a larger value. In the worst case that is O(n squared), because a long run of decreasing numbers makes every position scan all the way to the end. A stack solves the problem in O(n).

The stack holds the positions of numbers that are still waiting for a larger partner. Each waiting position is a question nobody has answered yet. When a new number arrives, it answers every waiting question whose value is smaller than it. Those positions are popped, and each one receives the new number as its answer. The new position then joins the waiting line on the stack. A stack whose values stay in one order from bottom to top is called a monotonic stack, and this is the classic example.

Type this into the Input box:

5
2 1 4 3 5

The output is:

4 4 5 5 -1

Trace the input 2 1 4 3 5. The first number, 2 at position 0, waits, so the stack holds 0. The 1 at position 1 is not larger than the waiting 2, so it also waits, and the stack holds 0 1 with the 1 on top. The 4 at position 2 is larger than the value on top, which is the 1 at position 1. The program records 4 as the answer for position 1 and pops it. It then compares 4 with the 2 at position 0, which is smaller, so 4 is the answer for position 0 as well. Both are popped, and the 4 waits at position 2. The 3 at position 3 cannot answer anything, so it waits above the 4. The final 5 answers the 3 at position 3 and then the 4 at position 2. The number 5 has no larger value to its right, so it stays at -1.

The reason the loop is fast is worth stating clearly. The while loop sits inside the for loop, and a learner may fear that this makes O(n squared). It does not. Each position is pushed exactly once and popped at most once. Count the pops across the whole run and you get at most n, no matter how many pops a single step makes. The total work is O(n).

The double loop is the simple answer, and it is correct. Interviewers still ask for the stack version, because it shows you can see the structure of the problem: the answer for an item depends only on the items that are still waiting. The same idea gives the next smaller value, by flipping the comparison, and it gives the largest rectangle under a histogram, which is a harder problem with the same stack at its heart.

Stack patterns that interviewers ask about

Three uses of the stack show up again and again in interviews.

• Matching pairs. Brackets, HTML tags and quotes all need the most recent unmatched opener. Push openers, pop on closers, and check the top.
• Remembering a choice to revisit. Depth-first search of a graph or a tree uses a stack, either explicitly or through recursion, to remember the path back.
• Next greater element. To find for each number the next larger number to its right, keep a stack of numbers that are still waiting for a larger one. Each number is pushed and popped at most once, so the whole job is O(n).

queue: first in, first out

A queue is the opposite of a stack. Items join at the back and leave from the front, so the item that has waited longest is always next. The operations are:

• push(x) adds x at the back. It is O(1).
• front() returns the value at the front. It is O(1).
• back() returns the value at the back. It is O(1).
• pop() removes the front value. It is O(1) and returns nothing, like the stack pop.

A queue is also an adaptor. By default it uses a deque underneath, so it can grow and shrink at both ends, but it exposes only the front and back for queue work. There is no index, and a range-based for does not compile on a queue. Pop in a loop to walk through it.

Queues drive breadth-first search, abbreviated BFS. BFS explores a space in rings. It visits every cell at distance 1, then every cell at distance 2, and so on. Because the queue is first in, first out, the ring that was discovered first is expanded first. That order is what makes BFS find the shortest number of steps in an unweighted grid, where every step costs the same.

The animation below shows a queue at work. Watch how the front advances and new items join at the back.

Worked example 4: the shortest path through a grid

A robot is in the top-left corner of a grid. Some cells are walls, marked #. The robot moves one cell at a time up, down, left or right, and it cannot enter a wall. The program finds the fewest moves needed to reach the bottom-right corner, or prints -1 if no path exists.

The program keeps a dist table, which records the distance of each cell from the start, with -1 meaning "not reached yet". It starts a queue with the start cell. Each time it takes a cell from the front, it looks at the four neighbours and adds any unvisited, open neighbour to the back with distance one more.

Type this into the Input box:

4 5
....#
.##.#
...#.
#....

The output is:

7

The program prints only the final distance, but the queue order decides it. Start with (0,0) at distance 0. It is the only item, so it is popped first, and its open neighbours join the queue at distance 1. Those are (1,0) below and (0,1) to the right.

Every time a cell leaves the front, its unvisited neighbours join the back at one more step. Because cells leave in the order they were discovered, every cell is discovered at its shortest distance the first time. When the target cell is reached, the answer is its stored distance. The path with seven moves goes down the first column to row 2, then right across row 2 to column 1, down to row 3, and right along row 3 to column 4. Another path with seven moves also exists, so the answer is the same either way.

The dist check is what makes the search finish. Without it, the program would revisit cells forever, because two neighbours can each point back to the other. The check dist[nr][nc] != -1 means "already discovered". That is the same as the visited flag you will see in graph problems.

The structured binding auto [r, c] = q.front(); copies the front pair before pop removes it. That order matters. If you wrote q.pop() first, the reference to the front would be gone.

Queue patterns that interviewers ask about

• Shortest path in an unweighted graph or grid. Use BFS with a queue and a visited marker. The first time you reach a cell, its distance is the shortest.
• Processing items in arrival order. Jobs, messages and requests are handled first in, first out, so a queue is the default.
• Level by level work. Process the whole queue in batches, using the size at the start of each batch, to group items by distance. This gives you the levels of a tree or of a grid.

priority_queue: the most important item first

A priority_queue always gives you the largest item under its ordering. It does not keep the items sorted. It keeps only the top item ready, and the rest are arranged in a structure called a heap. A heap is a binary tree stored in an array, where every parent is at least as large as its children. The diagram shows the idea: the largest value sits at the root, and each parent is at least as large as its children.

A max heap stored as a tree, with the largest value at the top and an array view below it

The costs are the heap costs:

• push(x) is O(log n). The new value goes at the bottom and rises past smaller parents until the heap rule holds.
• pop() is O(log n). The top is removed, the last value moves to the top, and it sinks down past larger children.
• top() is O(1). The largest value is always at the root.

The default priority_queue<int> is a max-heap, which keeps the largest value on top. For a min-heap, which keeps the smallest value on top, pass the comparison as a third template argument: priority_queue<int, vector<int>, greater<int>>. The middle argument is the container the heap lives in, and it must be a vector here. For pairs, the comparison is the usual pair order: first by first, then by second.

Step through the animation to see values rise and sink. The key idea is that a heap does not sort everything. It only promises the top. That promise is enough for many problems, and it costs much less than sorting every time a value arrives.

Worked example 5: the k largest numbers

Suppose a stream of numbers is too long to store, or it arrives one at a time, and you need the k largest. The clever trick is to keep a min-heap of size k. Its top is the smallest of the k largest seen so far. For each new number, push it. If the heap now has more than k items, pop the smallest. What remains is always the k largest numbers. This costs O(n log k), which is much better than sorting when k is small.

Type this into the Input box. The first line holds n and k, and the second line holds the numbers.

8 3
4 19 7 3 25 11 6 19

The output is:

25 19 19

Trace it. After the first three numbers, the heap holds 4 7 19. The number 3 is pushed, which makes four items, so the smallest, 3, is popped. The heap is 4 7 19 again, and then 25 comes in. The heap becomes 4 7 19 25, and popping the smallest leaves 7 19 25. Then 11 comes in, pops 7, and leaves 11 19 25. The number 6 is pushed and popped at once, because it is smaller than everything in the heap. The last number is 19. It is pushed, and the smallest, 11, is popped. The heap ends as 19 19 25.

The program pops the heap into a vector. Because the heap is a min-heap, the vector comes out smallest first, so 19 19 25. The loop prints the vector backwards, which gives the descending order 25 19 19. Two 19s appear because the input has two. A heap keeps duplicates, which is what you want when every score counts.

What happens inside a heap

When you push a value, the heap places it at the first free slot at the bottom of the tree. Then it compares the value with its parent. If the value is larger, they swap, and the comparison repeats one level up. This is called sifting up. It stops at the root or when the parent is larger. The work is at most the height of the tree, and the height is about log n for n items.

When you pop, the heap takes the root out, moves the last value into the root, and then compares it with its children. If a child is larger, the value swaps with the larger child and continues downwards. This is sifting down. Again the work is about log n.

Because the heap is stored in an array, parents and children are found by arithmetic on positions. The children of the item at position i sit at 2i+1 and 2i+2. That is why no pointers are needed, and why the heap uses memory as tightly as a vector.

Choosing between the three

The table below gives the right container for a common job. The question to ask is which item you need next.

Watch for the words "most recent" and "oldest". Most recent points at a stack. Oldest points at a queue. Largest or most urgent points at a priority queue. Interview problems often hide these words in a longer story, and finding them is half the job.

Interview view: what the costs tell you

Interviewers want you to state the cost and the reason. For the bracket check, say "O(n) time, because each character is pushed or popped at most once, and O(n) space in the worst case, when all characters are openers". For the grid search, say "O(R times C) time and space, because each cell enters the queue once". For the top-k heap, say "O(n log k) time and O(k) space". Those three answers cover most of the questions you will be asked about these containers.

A second skill is knowing when a heap beats sorting. Sorting n values costs O(n log n) and gives you everything in order. A heap costs O(n log k) to keep the top k, and it can work on a stream that never ends. If k is small compared with n, the heap wins. If you need all values in order, sorting is simpler and just as fast.

Common mistakes and the messages you will see

Mistake 1: using the result of pop. The stack pop returns nothing. A learner writes int x = s.pop(); and the compiler stops:

error: void value not ignored as it ought to be

The message says you used a void, which holds no value, as if it held one. Read the value with top() first, then call pop() on its own line.

Mistake 2: looping over a queue. A learner writes a range-based loop over a queue:

error: no matching function for call to 'begin(std::queue<int>&)'

The compiler looks for a begin function and finds none, because a queue has no iterators. Pop the items in a loop instead: while (!q.empty()) { int x = q.front(); q.pop(); ... }.

Mistake 3: reading top or front on an empty container. Calling top() or front() on an empty stack or queue is undefined behaviour. It does not throw an exception that you can catch. The program may print garbage, read freed memory or crash later. Always check empty() first. In the RPN program, the line int b = st.top(); is only safe because the expression is valid.

Mistake 4: forgetting that the heap is a max-heap. A learner writes priority_queue<int> pq; and expects the smallest value on top. The result is the largest, because that is the default. Add the three-argument form when you want smallest first.

Mistake 5: comparing the wrong thing with a pair. A learner pushes pair<string, int> into a priority queue and expects the lowest score first. The pair order compares the string first. The fix is to store the score first, or to write the comparison yourself.

Mistake 6: forgetting the visited check in BFS. Without a visited marker, a grid search pushes the same cell many times. The queue grows, the distances get overwritten, and the program may run for a very long time. The fix is the check dist == -1 before pushing.

Debugging walkthrough: a stack that comes out in the wrong order

A learner writes a function that checks whether a word reads the same forwards and backwards. They push every letter onto a stack, then compare the popped letters with the word, but the function says racecar is not a palindrome. Here is how to find the bug.

1. Print the stack before the comparison loop. The top is the last letter pushed, which is r for racecar. That part is right.
2. Compare the first letter of the word, r, with the top, r. They match. Pop.
3. Next the top is a, and the word's second letter is a. They match.
4. Look at the loop itself. It compares st.top() with word[i] and then increments i, but it never calls pop(). So the top stays r for every step. The comparison fails at the second letter.

The fix is to call pop() after each comparison, and to stop the loop when the stack is empty. Write the body as if (st.top() != word[i]) return false; st.pop(); i++;. Walking the code with a sample input, writing down the state after each line, finds this kind of bug quickly.

Variations and edge cases

A few details change the answer for beginners.

• A stack with no items returns true from empty(), so checking the bracket string "" returns true. The empty string is balanced by that rule, and an interviewer may ask you to state it.
• A top-k heap with k larger than the number of items keeps all items. Your loop must handle this, because the heap is never full.
• A top-k heap with k equal to zero is a special case. Check it before the loop, because heap.top() on an empty heap is undefined.
• A BFS start cell that is a wall, or a target that cannot be reached, gives -1 with the program above. Check the target distance before printing it, if your problem requires a different message.
• Two items with equal priority in a priority queue come out in no guaranteed order. If the order matters, add a second key, such as an arrival number, and compare both.

Practice

The solutions are hidden below each exercise. Try each one before you open it.

1. Reverse a string using a stack. Input stream. Expected output: maerts.

stack<char> st;
for (char c : string("stream")) st.push(c);
while (!st.empty()) {
    cout << st.top();
    st.pop();
}
cout << endl;

2. Print the jobs of a printer line in the order they were added. Push report, invoice, photo, then print and remove each job from the front. Expected output: report invoice photo.

queue<string> jobs;
jobs.push("report");
jobs.push("invoice");
jobs.push("photo");
while (!jobs.empty()) {
    cout << jobs.front() << " ";
    jobs.pop();
}
cout << endl;

3. Find the 3 largest values of the vector {5, 1, 9, 3, 7, 2} using a min-heap that never grows past 3 items. Print them in descending order. Expected output: 9 7 5.

priority_queue<int, vector<int>, greater<int>> heap;
for (int x : {5, 1, 9, 3, 7, 2}) {
    heap.push(x);
    if (heap.size() > 3) heap.pop();
}
vector<int> best;
while (!heap.empty()) { best.push_back(heap.top()); heap.pop(); }
for (int i = (int)best.size() - 1; i >= 0; i--) cout << best[i] << " ";
cout << endl;

4. Extend the RPN program so that a line with too few numbers prints error instead of crashing. Check the stack size before each operator. Input line + 3. Expected output: error.

if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
    if (st.size() < 2) return INT_MIN;
    // the old code follows
}

5. Use a stack to decide whether a string of a and b characters is a palindrome, using the first half on the stack. Input abba gives YES, and input abc gives NO.

string s = "abba";
stack<char> st;
size_t half = s.size() / 2;
for (size_t i = 0; i < half; i++) st.push(s[i]);
size_t start = (s.size() % 2 == 0) ? half : half + 1;
bool ok = true;
for (size_t i = start; i < s.size(); i++) {
    if (st.top() != s[i]) { ok = false; break; }
    st.pop();
}
cout << (ok ? "YES" : "NO") << endl;

6. Two steps: a queue holds 2, 4, 6. Pop one value, push 8, then print the front and the back. Expected output: 4 8.

queue<int> q;
q.push(2); q.push(4); q.push(6);
q.pop();
q.push(8);
cout << q.front() << " " << q.back() << endl;

7. Debug this. It should print the top of a stack after two pushes and one pop, but it prints nothing sensible. Find the bug.

stack<int> s;
s.push(1);
s.push(2);
int x = s.pop();
cout << s.top() << endl;

8. Use a priority queue of pairs to print tasks in order of priority, where a larger number means more urgent. Input tasks (2, "write"), (9, "fix"), (5, "test"). Expected output: fix, test, write, one per line.

priority_queue<pair<int, string>> tasks;
tasks.push({2, "write"});
tasks.push({9, "fix"});
tasks.push({5, "test"});
while (!tasks.empty()) {
    cout << tasks.top().second << endl;
    tasks.pop();
}

9. Find out whether a grid has a path from the top-left to the bottom-right, using a queue. Print YES or NO. Use the grid from the worked example, but add a wall at (1,0) and (0,1) so that the start is blocked in. Expected output: NO.

10. Explain why BFS finds the shortest path in an unweighted grid, but a stack-based depth-first search does not. Give a short answer of three or four sentences.

11. Two steps: a min-heap receives the values 8, 3, 5, 1. Pop the top twice and print the second value that comes out. Expected output: 3.

priority_queue<int, vector<int>, greater<int>> h;
for (int x : {8, 3, 5, 1}) h.push(x);
h.pop();
cout << h.top() << endl;

What you now know

• A stack is last in, first out. Use it for undo, bracket matching and any problem where the most recent item matters.
• A queue is first in, first out. Use it for arrival order and for breadth-first search, which finds shortest paths in unweighted grids.
• A priority queue gives the largest item first. It costs O(log n) per push or pop, and a min-heap of size k finds the k largest values of a stream in O(n log k).
• pop returns nothing, and top or front on an empty container is undefined behaviour. Check empty() first.
• Each container is an adaptor. It exposes only its working ends, which keeps the code honest about what the program is allowed to do.