Start learning free

LESSON 408 OF 568 · STACK

Implement Queue Using Stacks in C++: Amortized O(1) with Two Stacks

Practice O(1) amortized Read the full explanation

A queue hands its values back in the order they arrived, like a line at a shop: the first value pushed is the first one to leave. A stack does the opposite: the last value pushed leaves first. Build a queue out of two stacks, using only what a stack can do: add a value on top, look at or remove the top value, and check whether it is empty.

Implement the class MyQueue:

  • MyQueue() creates an empty queue.
  • push(x) adds the integer x at the back of the queue.
  • peek() returns the value at the front of the queue, without removing it.
  • pop() removes the value at the front of the queue and returns it.
  • empty() returns true if the queue holds no values, and false otherwise.

The input is a list of operations, applied in order to one new MyQueue. The output lists what the peek, pop and empty calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    push(1)
    push(2)
    peek()
    pop()
    empty()
Output: 1 1 false
Explanation:
1 arrived first, so it is at the front: peek() returns 1, and pop() removes it and returns it.
2 is still in the queue, so empty() is false.

Example 2:

Input:
    push(1)
    push(2)
    pop()
    push(3)
    peek()
    pop()
    pop()
    empty()
Output: 1 2 2 3 true
Explanation:
pop() returns 1, the first value pushed. 3 arrives next, but 2 has been waiting longer,
so peek() and the next pop() return 2, and only then does pop() return 3. The queue is empty again.

Example 3:

Input:
    empty()
    push(7)
    empty()
    pop()
    empty()
Output: true false 7 true
Explanation: A new queue is empty. After push(7) it isn't, and after pop() returns 7 it is empty again.

 

Constraints:

  • 1 <= x <= 109
  • pop and peek are only called when the queue is not empty.
  • At most 2 * 105 calls in total are made to push, pop, peek and empty.

Note:

Each operation should take O(1) time amortized: one pop or peek may have to move many values from one stack to the other, but each value is moved at most once, so n operations take O(n) time in total. Moving all the values over and back again on every pop would take O(n) time per call, where n is the number of values in the queue.

STEP 1 OF 11
    Ctrl + Enter to check

    C++ · STACK

    Implement Queue Using Stacks in C++, explained

    Problem overview

    A queue gives values back in the order they arrived, like a line at a shop. A stack gives back the newest value first. The task is to build the queue class MyQueue from two stacks, using only what a stack offers: add on top, look at or remove the top, and check whether it is empty.

    The class has four methods: push(x) adds x at the back, peek() returns the front value without removing it, pop() removes the front value and returns it, and empty() says whether the queue holds nothing. pop and peek are only called on a non-empty queue.

    In the second example the calls are push(1), push(2), pop(), push(3), peek(), pop(), pop(), empty(). They return 1 2 2 3 true. The value 2 has been waiting longer than 3, so it leaves first.

    The statement asks for O(1) time per operation, amortized: one call may be slow, but a long run of calls is fast on average.

    Approach: one stack to receive, one to give back

    Pushing is easy. The problem is the front: the oldest value sits at the bottom of the stack that received the pushes, and a stack only gives access to its top.

    Moving every value from one stack to another reverses their order. Values pushed 1, 2, 3 sit in the first stack with 3 on top. Move them one by one onto a second stack and 1 is on top, ready to leave first. That reversal turns stack order into queue order.

    The simple version does this move on every pop and moves all the values back afterwards. A pop then costs O(n): with 1,000 pushes followed by 1,000 pops, that design makes 1,000,000 moves.

    The better idea is to not move the values back. Keep two stacks:

    • inStack receives every pushed value, with the newest on top;
    • outStack holds values in leaving order, with the oldest on top.

    Values move from inStack to outStack only when outStack is empty and the front is needed. While outStack still has values, all of them arrived before anything in inStack, so its top is still the front of the queue.

    Why this is amortized O(1)

    Count the moves per value. Each value is pushed once onto inStack, moved at most once to outStack, and popped once from outStack. It never moves back. So a value costs at most three constant-time operations in its whole life. For n operations, the total work is O(n), and one slow pop that moves many values is paid for by the many cheap calls before it. After 100,000 pushes followed by 100,000 pops, the design moves exactly 100,000 values, one move per value.

    Here is the second example's state after each step (the top of a stack is its last value):

    push(1), push(2): inStack [1 2]   outStack []
peek() = 1:       inStack []      outStack [2 1]
pop() = 1:        inStack []      outStack [2]
push(3):          inStack [3]     outStack [2]
peek() = 2:       inStack [3]     outStack [2]
pop() = 2, then pop() = 3: both stacks empty

    The second peek moves nothing: outStack still has the 2, which is older than the 3. Only the last pop moves the 3 across.

    Step by step

    1. Declare inStack as a stack<int>. Every pushed value goes on top of it.
    2. Declare outStack as a second stack<int>. Values leave from it, oldest on top.
    3. In push, push x onto inStack. The new value joins the back of the queue.
    4. In peek, check whether outStack is empty. Only then is a move needed.
    5. Loop while inStack is not empty. Every value in it must move, so that the oldest one ends up on top.
    6. Move one value: push inStack.top() onto outStack, then pop inStack. In C++, pop() removes the top but returns nothing, so the value is read with top() first.
    7. Return outStack.top(). Whether values were just moved or not, the oldest value is on top. Reading it removes nothing.
    8. In pop, store peek() in front. peek already moves values when needed and finds the front.
    9. Pop outStack. After peek, its top is the front, so this removes the front.
    10. Return front, which was read before the removal.
    11. In empty, return whether both stacks are empty, joined with &&. The queue's values are split between them.

    The solution in C++

    class MyQueue {
public:
    stack<int> inStack;
    stack<int> outStack;

    void push(int x) {
        inStack.push(x);
    }

    int peek() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }

    int pop() {
        int front = peek();
        outStack.pop();
        return front;
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

    The C++ details worth a closer look:

    • std::stack. stack<int> has exactly the operations the task allows: push, top, pop, empty (and size). It has no indexing and no iterators.
    • pop() returns void. In some languages a stack's pop returns the removed value. In C++ you read with top() and then call pop(). That is why the move loop has two lines and why MyQueue::pop saves peek() before removing.
    • top() and pop() on an empty stack are undefined behaviour. The constraints promise that pop and peek are called on a non-empty queue, so after the move outStack is never empty.
    • A method calling a method. Inside the class, peek() is called by its name alone, on the same object.
    • The names. The class's own push and pop share their names with the stack's, but inStack.push(x) and MyQueue::push(x) are different functions, chosen by the object before the dot.

    A run on the third example gives true false 7 true for empty(), push(7), empty(), pop(), empty().

    Complexity

    Time: O(1) amortized per operation. push and empty are O(1). A single peek or pop can cost O(n) when it moves all n waiting values. But each value moves from inStack to outStack at most once in its life, so any sequence of m operations makes at most m moves, which is O(m) in total.

    Space: O(n). The two stacks together hold exactly the n values in the queue, with each value in one stack at a time.

    Edge cases and common mistakes

    • Moving while outStack is not empty. If values from inStack were put on top of the old ones, the order would break. In the second example, 3 would land above 2 and leave first.
    • Moving back after each pop. It keeps the order right but makes every pop cost O(n): 1,000 pushes followed by 1,000 pops make 1,000,000 moves.
    • empty checking only one stack. After push(1) and peek(), inStack is empty but the queue is not. After push(1) alone, outStack is empty and the queue is not either.
    • Calling pop() on a stack and expecting a value. In C++ it returns nothing. The code int front = outStack.pop(); does not compile.
    • Peeking without moving. If peek returned inStack.top(), it would give the newest value, not the oldest.
    • Interleaved pushes and pops. A push between two pops goes to inStack and waits. It crosses over only after outStack has run dry.

    Testing

    • push(1), push(2), peek(), pop(), empty() gives 1 1 false.
    • push(1), push(2), pop(), push(3), peek(), pop(), pop(), empty() gives 1 2 2 3 true.
    • empty(), push(7), empty(), pop(), empty() gives true false 7 true.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free