Start learning free

LESSON 409 OF 569 · STACK

Implement Queue Using Stacks in Java: Amortized O(1)

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

    JAVA · STACK

    Implement Queue Using Stacks in Java, explained

    Problem overview

    A queue gives values back in the order they arrived, like a line at a shop. A stack does the opposite: the last value pushed leaves first. The task is to 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.

    The class MyQueue has four methods. push(int x) adds x at the back. peek() returns the front value without removing it. pop() removes the front value and returns it. empty() returns true if the queue holds no values. The constraints say pop and peek are only called on a non-empty queue. The tests print booleans as True and False, while Java's own spelling is true and false.

    Here is a session. 1 arrived before 2, so it leaves first. 3 arrives after 2, so 2 is still the front when 3 is pushed.

    MyQueue q = new MyQueue();
q.push(1);
q.push(2);
System.out.println(q.pop());
q.push(3);
System.out.println(q.peek() + " " + q.pop() + " " + q.pop() + " " + q.empty());

    1
2 2 3 true

    Approach: reverse the order once, by moving values

    Popping a stack gives the newest value first, but a queue needs the oldest. Moving values from one stack to another reverses their order: the newest value leaves the first stack first and lands at the bottom of the second, and the oldest leaves last and lands on top. So the second stack has the oldest value on top, which is the front of the queue.

    The simple version moves everything on every pop: move all values to the second stack, pop its top, then move everything back. Each pop then costs O(n) for n values in the queue.

    The better idea is to not move them back. The lesson uses two stacks with fixed roles:

    • inStack takes every pushed value. Its top is the newest value.
    • outStack gives values back. Its top is the oldest value, the front of the queue.

    A value is moved only when outStack is empty and the front is needed. While outStack still holds values, they all arrived before anything in inStack, so its top is still the front and nothing has to move. The queue's values are split between the two stacks, with the older ones in outStack.

    Here is the state of the two stacks (Java prints a Stack from bottom to top) after pushing 1, 2 and 3, after a peek(), and after one more push of 4. The code reads the fields directly, which a user of the class would not do.

    MyQueue q3 = new MyQueue();
q3.push(1); q3.push(2); q3.push(3);
System.out.println("in=" + q3.inStack + " out=" + q3.outStack);
System.out.println(q3.peek());
System.out.println("in=" + q3.inStack + " out=" + q3.outStack);
q3.push(4);
System.out.println("in=" + q3.inStack + " out=" + q3.outStack);

    in=[1, 2, 3] out=[]
1
in=[] out=[3, 2, 1]
in=[4] out=[3, 2, 1]

    The peek() moved all three values over and their order flipped, so 1 is on top of outStack. The 4 waits in inStack and will be moved only after 1, 2 and 3 have left. Three pops return 1, 2 and 3, and the next pop moves the 4 over and returns it.

    Why it is amortized O(1)

    One pop or peek may move many values, so a single call can be slow. But look at one value's life: it is pushed onto inStack once, moved to outStack at most once, and popped from outStack once. Three operations in total, whatever the sequence of calls. A value is never moved back, because the stacks have fixed roles.

    So n operations cause at most about 3n stack operations in total, which is O(n), and O(1) per operation on average. This is called amortized O(1). To see it concretely, take a queue where 1,000 values are pushed, and after every third push a pop is done, and finally the rest is popped. That is 1,000 pushes and 1,000 pops, and the total number of moves between the stacks is exactly 1,000, one per value, even though the single most expensive call moved 637 values. The cost of that call is paid for by all the cheap calls around it.

    Step by step

    1. Declare inStack, a Stack<Integer> starting empty. Every pushed value goes on top of it.
    2. Declare outStack the same way. The values leave from it, oldest on top.
    3. push: push x onto inStack.
    4. peek: write an if for when outStack is empty. Values move only then.
    5. Inside it, loop while inStack is not empty.
    6. In the loop, pop the top of inStack and push it onto outStack, in one line. The newest value leaves first and lands deepest, so the oldest ends up on top.
    7. After the if, return outStack.peek(). Whether values were just moved or not, the oldest value is on top, and reading it removes nothing.
    8. pop: call this class's own peek() and keep the result in front. That moves values when needed and finds the front.
    9. Pop the top of outStack, which removes the front.
    10. Return front, which was read before it was removed.
    11. empty: the values are split between the stacks, so the queue is empty only when both are: inStack.isEmpty() && outStack.isEmpty().

    The solution in Java

    class MyQueue {
    Stack<Integer> inStack = new Stack<>();
    Stack<Integer> outStack = new Stack<>();

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

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

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

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

    A few details about the Java code:

    • java.util.Stack. It has push, pop, peek and isEmpty, all working at the top. pop and peek on an empty Stack throw EmptyStackException, which the constraints rule out.
    • Printing a Stack. It prints from the bottom to the top, so [3, 2, 1] has 1 on top.
    • Calling peek() from pop(). Inside a class a method calls another method of the same object by its name alone. pop reuses all of peek's work.
    • Boxing. The stacks hold Integer objects. push(int x) boxes on the way in, and int front = peek() unboxes on the way out, because the methods return int.
    • Everyday Java. Outside this exercise, a queue is an ArrayDeque or a LinkedList, both of which implement Queue. The exercise is about building one from stacks.

    Seeing it work

    A new queue is empty. After push(7) it is not, and after pop() returns 7 it is empty again.

    MyQueue q2 = new MyQueue();
System.out.println(q2.empty());
q2.push(7);
System.out.println(q2.empty());
System.out.println(q2.pop());
System.out.println(q2.empty());

    true
false
7
true

    Note that empty() checks both stacks. After push(7) the value sits in inStack and outStack is empty. After a peek() the value is in outStack and inStack is empty. In both states the queue is not empty.

    Complexity

    Time: amortized O(1) per operation. push and empty are always O(1). peek and pop take O(1) when outStack has values, and O(m) when they must move m values. Each value is moved at most once in its lifetime, so n operations take O(n) in total. Moving all the values over and back on every pop would take O(n) per call.

    Space: O(n) for the n values currently in the queue, spread over the two stacks.

    Edge cases and common mistakes

    • Moving values while outStack still has some. This breaks the order. If outStack holds 2 and a newer 3 sits in inStack, moving 3 on top of 2 would make 3 leave first.
    • Moving values back. Putting everything back into inStack after each pop works, but each call is then O(n).
    • Checking only one stack in empty(). The values can be in either stack.
    • Removing in peek. peek must read the top of outStack without popping it. Only pop removes.
    • Using || instead of && in empty(). That would call the queue empty when only one stack is.
    • Interleaved pushes and pops. A push after some pops goes on inStack and waits until outStack runs out, as the 4 did above. This is what keeps the order right.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free