Queues and building a queue from two stacks

Why it matters

Queues drive breadth-first search in graphs, task schedulers, print spoolers, and any system where work must be served in the order it arrived. In interviews, "implement a queue using stacks" is a classic problem because it tests whether you understand both structures well enough to see that a stack reverses order, and that two reversals restore it. This lesson gives you the queue itself, a linked-list version that shows the memory details, the two-stack trick with a careful cost argument, and two small programs that use queues to solve real-looking problems.

The idea: first in, first out

A stack serves the newest item first. A queue does the opposite. It serves the oldest item first. The rule is called FIFO, which stands for first in, first out.

Picture a line at a ticket counter. People join at the back. The clerk serves the person at the front. Nobody can cut in, and nobody can leave from the middle. The person who waited longest is served first, and the newest arrival waits the longest of all. That is the whole rule, and it is the reason queues feel fair.

A queue has these operations:

• push(x), also called enqueue: add x at the back.
• pop(), also called dequeue: remove the item at the front.
• front(): read the item at the front without removing it.
• back(): read the item at the back without removing it.
• empty() and size(): check whether the queue is empty, and how many items it holds.

Like a stack, a good queue does each of these in O(1) time, which means constant time regardless of how many items are inside. The words "push" and "pop" are used for both structures, so always check which one you are using. For a queue, pop removes the oldest item, not the newest.

Step through the next visualizer. Watch the first item added leave first, even when new items keep arriving at the back.

Notice what does not happen in the animation. No item ever moves from its place in the line. New items join at the back, and the front item leaves. That stability is what makes queues cheap to use, and it is also the reason they need a memory structure that can grow at the back and shrink at the front.

The standard library queue

C++ provides std::queue in the <queue> header. It has the same operations as the diagram above, with the names push, pop, front, back, empty and size.

Output:

1 3
2 2

Read the first line carefully. front() returns 1, because 1 was added first and it is the oldest item. back() returns 3, because 3 was added last. After pop() removes the 1, the new front is 2, and the queue holds two items.

Like std::stack, std::queue is an adapter. By default it stores its items in a std::deque, which you will meet at the end of this module. The adapter only exposes the queue operations, so you cannot accidentally index into the middle of a queue. That limit is useful: a queue that allowed random access would no longer be a queue.

Calling front() or pop() on an empty queue is undefined behaviour, just as it is for a stack. With the optional safety checks turned on, the library stops the program and prints a message. Here is the message from g++ when the check catches an empty queue, shortened to fit:

/usr/include/c++/15/bits/stl_queue.h:262: ... front() ...: Assertion '!this->empty()' failed.

The exit code is 134. The safety check is a teaching tool, and a real program should test empty() before every front() and pop().

What happens inside: a linked-list queue

A queue is easy to picture as a line, but the memory can be arranged in more than one way. One natural way uses a linked list. A linked list is a chain of small blocks called nodes. Each node holds a value and a pointer to the next node. A pointer is a variable that stores the address of another block in memory. The last node points to nothing, which C++ writes as nullptr.

A queue needs two pointers into the chain: head points to the front node, and tail points to the back node. Pushing attaches a new node after tail. Popping removes the node at head. Neither operation moves any other node, so both are O(1).

The program below builds that queue. Read the Node struct first. It has a value called data and a pointer called next. The constructor sets next to nullptr, which means "no next node yet".

Output:

5 6 1

Trace it. The first push(5) finds tail equal to nullptr, so the else branch sets head to the new node, and tail also points to it. The second push(6) finds tail set, so it writes the new node's address into tail->next, and then moves tail to the new node. The chain now reads 5, then 6. The first pop() takes the node at head, which holds 5, moves head to the next node, and frees the old node with delete. The second pop() does the same with 6. When head becomes nullptr, the line if (!head) tail = nullptr; clears tail as well.

That last line matters. If you remove it, tail still points to the node you just deleted. The next push would write into memory that no longer belongs to the queue, which is undefined behaviour and usually a crash. This kind of bug is hard to find, because the program may run correctly for a while. The rule to remember is that every time head changes to nullptr, tail must change too.

The destructor, the function named ~Queue, runs when the queue goes out of scope. It pops until the queue is empty, so every node is freed. Without it, the nodes would be left in memory, which is a memory leak. A leak means memory is taken and never given back, so a long-running program slowly grows.

The linked version is O(1) for every operation, and it never has a fixed capacity. Its cost is the pointer in each node, plus the time to ask the system for each new node. An array version, as in the circular queue lesson, stores items next to each other and is faster in practice, but it needs a fixed size or a more careful growth plan.

Building a queue from two stacks

Here is the central problem of this lesson. You are allowed to use only stack operations: push, pop, top and empty. Build a queue from them.

The key fact is that a stack reverses order. If you push 1, 2, 3 and then pop them all, you get 3, 2, 1. The newest item comes out first, which is the wrong order for a queue. But a second reversal would fix it. If you pour the stack into another stack, the order flips again, and the oldest item ends up on top.

Use two stacks. Call them in and out.

• push(x) puts x on in. Pushing is always cheap, and nothing is moved.
• pop() and front() look at out. If out is empty, move every item from in into out. Moving pops one stack and pushes onto the other, which reverses the order. After the move, the oldest item sits on top of out, and you can pop or read it.
• The rule for the move is strict: move items only when out is empty. If out still holds older items, the new items would land on top of them and break the order.

Here is the picture of two pushes, one pop and the move that follows.

Two stacks named in and out. Pushing 1 and 2 fills in, then a pop moves both into out, so 1 sits on top of out and comes off first

The program below implements that idea and uses it on a short sequence of operations.

Output:

1
1
2
3
4
1

Trace the first two lines. push(1) and push(2) put 1 and then 2 on in, so in holds the items with 2 on top. front() calls shift(). The out stack is empty, so the code pops 2 off in and pushes it onto out, then pops 1 off in and pushes it onto out. Now out has 1 on top, and front() returns 1. The output's first line is 1.

Continue the trace. front() did not remove the 1, so out now holds 2 and then 1 on top. push(3) puts 3 on in. The first pop() calls shift(), but out is not empty, so nothing moves. It removes the 1, which prints the second line. The second pop() removes the 2 from out, which prints the third line. Then the code pushes 4. The next pop() finds out empty, so it moves 3 and 4 from in into out. The 3 ends up on top, so that pop prints 3, and the next pop prints 4. The last line prints 1, because empty() is true when both stacks are empty.

Why it is amortised O(1)

A single pop() can be expensive. When out is empty and in holds n items, the move loop does n pops and n pushes. So one call can cost O(n). Calling it "O(1)" sounds like a lie.

The honest statement is about the average over many operations, and the word for it is amortised. Count how many times each item moves. An item is pushed onto in once. It moves from in to out at most once, because after the move out is only popped, never refilled, until it is empty again. After it moves, it is popped from out. So each item takes part in at most three moves in its whole life: one push, one transfer, one pop. Over a sequence of n operations, the total work is at most about 3n. Dividing by n gives a constant average, which is O(1) amortised.

Think of it as a bill that is paid in advance. Each push pays a little extra toward the future transfer. When the transfer happens, the money is already there. No single operation is secretly always expensive, and the average cost stays flat no matter how long the sequence runs.

Amortised does not mean average over random input. It is a guarantee over any sequence. Even the worst input cannot make the total cost more than the bound. That is why interviewers accept the statement, as long as you explain the argument.

Round-robin scheduling: a queue at work

A queue is the natural structure for fair scheduling. Imagine a computer with one processor and three tasks. Each task needs some time units. The scheduler gives each task a slice of at most q units, then moves it to the back of the line if it is not finished. This is called round-robin scheduling, because the processor visits the tasks in a repeating order.

Here is a worked example. The quantum q is 2, and the tasks are A needing 5 units, B needing 3, and C needing 1.

So C finishes at time 5, B finishes at time 8, and A finishes at time 9. The program below does exactly this. Its input is the first line with n and q, then one line for each task with its name and its time units. Type the Input box exactly as shown.

Input box:

3 2
A 5
B 3
C 1

Output:

C finishes at 5
B finishes at 8
A finishes at 9

The output order is not the order the tasks were entered. C finishes first, because it needs only one unit and it reached the front quickly. This is what fairness looks like in practice: short tasks finish early, and long tasks still make steady progress. The queue guarantees that no task waits forever, because every unfinished task goes to the back and must reach the front again.

Notice the design choice line.push(t) for unfinished tasks. The task object is copied into the queue with its new left value. The queue stores whole objects, not pointers, so each entry carries its own remaining time. Copying is simple here, and the queue of structs is clear to read.

Generating binary numbers with a queue

A queue can also drive a counting process. Here is a classic trick. Start with the queue holding "1". Repeatedly take the front, print it, and add two children, the same string with 0 added and with 1 added. The first numbers the queue produces are the binary numbers in increasing order, because a shorter number always comes out before a longer one, and within one length the order follows the parent order.

For n = 5, the output is 1 10 11 100 101. The program reads n and prints the first n binary numbers. Type 5 in the Input box.

Input box:

5

Output:

1 10 11 100 101

Trace the queue contents. It starts as 1. The first iteration prints 1 and adds 10 and 11. The second prints 10 and adds 100 and 101. The third prints 11 and adds 110 and 111. The fourth prints 100, and the fifth prints 101. The queue is never used as a stack here. The order of printing is the order of adding, which is exactly FIFO.

Debugging walkthrough: a queue that serves the wrong item

Here is the buggy version of the two-stack queue. Its shift function moves items even when out still holds older items. Predict the output before you run it. The correct output is 1, 2, 3.

Output:

1
3
2

The first pop is correct. The second pop is wrong. After the first pop, out still holds 2 on top. Then push(3) puts 3 on in. The second pop calls shift, which moves 3 onto out on top of the 2. The pop then returns 3, which is the newest item. The queue served the newest item first, which is exactly the behaviour a stack has.

To find this bug, trace the state after each operation. Write down the contents of in and out as lists, with the top on the right. After the first pop, out holds one item, the 2. The in stack is empty. Then push(3) makes in hold the 3. A correct refill would wait, because out still holds the 2. The buggy shift moves the 3 anyway, so the 3 lands on top of the 2. Adding that check to shift fixes the bug, and the output becomes 1, 2, 3.

Tracing the linked queue step by step

The linked queue is easier to trust once you have followed its pointers through a short sequence. The table below runs push(5), push(6), pop(), pop() and empty(), the same sequence as the program. The list column shows the values in the chain from head to tail.

The printed line is 5 6 1. There is one detail about the order of evaluation that matters here. The line is cout << q.pop() << " " << q.pop() << " " << q.empty(). Since C++17, the parts of a chain of << operators are evaluated from left to right. So the first pop() runs before the second one, and the first printed value is 5. Before C++17 the order was not guaranteed, and the same line could print 6 first. Writing one pop() per line removes any doubt, and that is a good habit when a line has side effects.

Notice step 3 more closely. The node A is freed, but B is not touched. The queue never moves a node, which is why both operations are O(1). Notice also step 4. The line if (!head) tail = nullptr; runs only in this step, because it is the only step that empties the queue. A reader who skims the code can miss it, so put a comment on it, as the program does.

Breadth-first search with a queue

The most important real use of a queue in this course is breadth-first search, usually written BFS. It explores a graph in rings. First it visits the start, then every node one step away, then every node two steps away, and so on. A graph is a set of nodes joined by edges, such as cities joined by roads. A queue makes the rings happen in order, because the nodes found first are processed first.

Take a small graph with five nodes. A is joined to B and C. B is joined to A and D. C is joined to A and D. D is joined to B, C and E. E is joined to D only. Start the search at A, and always take neighbours in alphabetical order.

The method has three rules. Keep a queue of nodes waiting to be processed, and a set of nodes already seen. Start with the start node in the queue and marked as seen. Repeatedly take the front node from the queue, process it, and add each of its neighbours that is not yet seen to the back of the queue, marking each one as seen when it is added.

The visit order is A, B, C, D, E. Notice that D was added to the queue once, even though B and C both lead to it. The seen set stops the duplicate. Without it, D would be added twice, and the search would do extra work and could loop forever in a graph with cycles.

The queue also gives the distances. A is at distance 0. B and C are at distance 1, because they were added when A was processed. D is at distance 2, because it was added when B (distance 1) was processed. E is at distance 3. The first time a node is seen, the search has found a shortest path to it, and that is why BFS is the standard method for shortest paths in graphs with equal edge costs.

This is the FIFO rule at work. If the queue were a stack, the search would follow one branch deep before returning, which is depth-first search. The depth-first search is also useful, but it does not give shortest distances. You will meet both in the graph lessons, and the difference between them is the difference between a queue and a stack.

Queue or priority queue?

A queue serves items strictly in arrival order. Sometimes the order should depend on something else, such as urgency. A hospital emergency room does not serve patients in arrival order, because the most critical patient is seen first. That structure is a priority queue. The C++ library has one called std::priority_queue, declared in the <queue> header. It is usually built on a heap, which you will meet in the heap module of this course.

The difference matters in interviews. If a problem says "serve the first one who arrived", use a plain queue. If it says "serve the most urgent", use a priority queue. A plain queue used for an urgency problem gives an answer that looks right on small examples, then breaks when a later arrival is more urgent than an earlier one. Read the rule in the statement, and say the order out loud before you choose the structure.

A checklist for reading queue code

When you review someone else's queue code, or your own after a day away, check these points in order.

• Does push add at the back, and does pop or front read from the front?
• Does every front() and pop() have an empty() test before it, or a guarantee that the queue is not empty?
• In a linked queue, when head becomes nullptr, does tail also become nullptr?
• In a two-stack queue, does the transfer run only when out is empty?
• When the code needs the value of a pop, does it read the value before removing it?
• Are the headers <queue>, <stack> and <iostream> present for the containers and streams used?

These six checks catch most queue bugs in practice. They take less time than a debugger, and they point at the lines where the rules are easy to break.

Common mistakes and the messages you will see

Mistake 1: refilling out when it is not empty. This is the bug above. The rule is that items move only when out is empty. Put the check at the start of shift, and never remove it.

Mistake 2: forgetting to reset tail. In a linked queue, when the last node is removed, head becomes nullptr, and tail must become nullptr too. The line if (!head) tail = nullptr; does this. Without it, the next push writes into freed memory, which is undefined behaviour.

Mistake 3: calling front() or pop() on an empty queue. The safety check prints the message shown earlier, with the assertion text and exit code 134. Test empty() first.

Mistake 4: confusing queue and stack. queue::front is the oldest item, and stack::top is the newest. Both are read with a function that has a similar name, so the difference is easy to miss. Say aloud which order you need before you choose the structure.

Mistake 5: forgetting the headers. Using queue<int> without #include <queue> gives the same kind of message as a missing stack include. The compiler says the name is not declared in this scope, and it points at the first use of the name. Add the include at the top.

Mistake 6: using pop expecting a value. Like std::stack::pop, std::queue::pop returns nothing. Read front() first, then call pop().

Interview questions and what they test

Interviewers ask about queues for three reasons: to check the FIFO rule, to test the two-stack trick, and to see whether you can argue about amortised cost.

• Implement a queue using two stacks. Describe in and out, the refill rule, and the amortised argument. Mention that the refill happens only when out is empty.
• Implement a stack using two queues. The answer is to rotate: after each push, move the older items behind the new one, so the newest is at the front. This costs O(n) per push, and it shows that the two-queue route is more expensive.
• Why is the worst case of a single pop O(n)? Because one call may move every item, but each item moves only once in its life.
• What is the cost of the linked version? O(1) for each operation, plus memory allocation for each push.
• How do you find the shortest path in a grid? A queue drives breadth-first search. Every cell is added to the back when it is discovered, and the front is processed first, so cells are visited in order of distance. The graph lessons of this course cover that search in detail.

Real-world uses

Print spoolers serve documents in the order they were sent. Message brokers hold messages in a queue until a worker reads them. Operating systems use queues for waiting input and output requests. Web servers hold incoming requests in a queue when all workers are busy. In each case, the rule first in, first out keeps the service fair and predictable.

Practice

1. Easy. Simulate a queue with the operations push 4, push 5, push 6, pop, front. What does front return, and why?

2. Easy. What does this print?

queue<int> q;
q.push(7);
q.push(8);
cout << q.back() << " " << q.front();

3. Easy. In the linked-list queue, what goes wrong if pop forgets to set tail to nullptr after the last node is removed? Describe it in plain words.

4. Medium. Implement a stack using two queues. Hint: after each push, move everything from the first queue into the second, then swap the names of the two queues.

5. Medium. Reverse a queue using a stack. Hint: move every item from the queue onto a stack, then move them back.

6. Medium. Generate the first n binary numbers with the queue method, but print them in a single line separated by commas. Hint: change the separator and the first line.

7. Medium. Write a function that takes a queue of integers and returns the sum of its items without changing the queue. Hint: move items to a second queue as you add them up, then move them back.

8. Hard. Design a queue that supports push, pop, and a function minimum() that returns the smallest item in the queue, all in amortised O(1). Hint: keep a second deque of candidate minimums. This is harder than the rest, so take your time.

9. Hard. Explain why the two-stack queue has amortised O(1) operations, but a single worst-case pop is O(n). Use the bill idea from this lesson in your answer.

10. Hard. Simulate the round-robin scheduler with tasks A (4 units), B (4 units), C (1 unit) and quantum 2. Write down the finish time of each task. Hint: keep a table like the one in this lesson.

What you now know

• A queue is FIFO: the oldest item leaves first, and new items join at the back.
• push and pop mean enqueue and dequeue for a queue, and they remove the oldest item.
• A linked-list queue keeps head and tail pointers, and must reset tail when the queue empties.
• Two stacks make a queue: push onto in, and refill out from in only when out is empty.
• The two-stack queue has amortised O(1) operations, because each item moves at most once between stacks.
• A queue of waiting tasks gives fair round-robin scheduling, and a queue drives breadth-first search.