Start learning free

LESSON 409 OF 569 · STACK

Implement Queue Using Stacks in Python: Amortized O(1) with Two Lists

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

    PYTHON · STACK

    Implement Queue Using Stacks in Python, 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 class MyQueue out of two stacks, using only what a stack does: add on top, look at or remove the top, and check whether it is empty. The methods are:

    • push(x) adds x at the back of the queue.
    • peek() returns the front value without removing it.
    • pop() removes the front value and returns it.
    • empty() returns True if the queue holds nothing.

    The tests call peek and pop only on a non-empty queue. Example: after push(1) and push(2), peek() returns 1 and pop() returns 1, because 1 arrived first. Then empty() is False, since 2 is still waiting. The tests print booleans as True and False, which is also how Python spells them.

    Approach: reverse once, and only when needed

    A stack's top is its newest value, but a queue needs its oldest one. Moving values from one stack to another reverses their order: the newest value leaves first and lands deepest, and the oldest leaves last and ends up on top. So a second stack can turn stack order into queue order.

    A simple version does this on every operation: move everything to the second stack, take the top, and move everything back. Each pop then costs O(n).

    The better version moves values lazily with two stacks:

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

    Values are moved from inStack to outStack only when outStack is empty. While it still holds values, all of them arrived before anything in inStack, so its top is still the front. New values can pile up in inStack and wait.

    Why each operation is amortized O(1)

    A single peek or pop can move many values, so one call can cost O(n). But each value moves at most once: it is pushed on inStack, moved to outStack once, and popped from there. A value on outStack never goes back. So n operations make at most n moves in total, and the average cost per operation is constant. That is what amortized O(1) means.

    A counting version of the class confirms it. After 1,000 rounds of 50 pushes followed by 30 pops (80,000 operations), the total number of moves was 39,800, fewer than the 50,000 values pushed. With 100,000 pushes and then 100,000 pops, the total was exactly 100,000 moves, one per value.

    Step by step

    1. In __init__, set self.inStack to an empty list. The top of the stack is the end of the list, because append and pop both work at the end.
    2. Set self.outStack to an empty list too. The values in it are already in leaving order, oldest on top.
    3. In push, append x to self.inStack.
    4. In peek, write an if for when self.outStack is empty. An empty list counts as false, so not self.outStack is true then.
    5. Inside it, loop while self.inStack has values.
    6. In the loop, pop the top of self.inStack and append it to self.outStack in one line. This is the move that reverses the order.
    7. Back at the method's level, return self.outStack[-1]. Reading it removes nothing.
    8. In pop, call self.peek() and keep the result in front. peek already moves values if needed.
    9. Pop the top of self.outStack, which is that front value.
    10. Return front.
    11. In empty, the values are split across two stacks, so the queue is empty only when both are: not self.inStack and not self.outStack.

    The solution in Python

    class MyQueue:
    def __init__(self):
        self.inStack = []
        self.outStack = []

    def push(self, x: int) -> None:
        self.inStack.append(x)

    def peek(self) -> int:
        if not self.outStack:
            while self.inStack:
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]

    def pop(self) -> int:
        front = self.peek()
        self.outStack.pop()
        return front

    def empty(self) -> bool:
        return not self.inStack and not self.outStack

    Watching the two stacks as the queue is used:

    q = MyQueue()
q.push(1)
q.push(2)
q.push(3)
print(q.inStack, q.outStack)
print(q.peek())
print(q.inStack, q.outStack)
q.push(4)
print(q.inStack, q.outStack)
print(q.pop(), q.pop(), q.pop(), q.pop(), q.empty())

    [1, 2, 3] []
1
[] [3, 2, 1]
[4] [3, 2, 1]
1 2 3 4 True

    The three pushed values sit in inStack in arrival order. The first peek moves them all, which reverses them: 1 is now on top of outStack. The later push(4) waits in inStack and doesn't disturb the order. Only when outStack runs dry does the 4 move over, and the values come out as 1, 2, 3, 4.

    Python details worth knowing:

    • A list works as a stack because append and pop() both act on the end in O(1). pop(0) would act on the front and cost O(n), so the code never uses it.
    • Inside a method, another method of the same object is called through self, as pop does with self.peek().
    • Only append, pop(), [-1] and emptiness checks are used, which are exactly the stack operations the task allows.

    Complexity

    Time: push and empty are O(1). peek and pop are O(1) amortized: one call may move all n values, but every value moves at most once, so a series of n operations costs O(n) in total.

    Space: O(n), for the n values held across the two stacks.

    Edge cases and common mistakes

    • Moving when outStack isn't empty. New values would land on top of older ones, and the order would break. In the example above, moving the 4 while outStack still holds 3, 2 and 1 would put it on top, and it would leave before them.
    • Moving back and forth. Pushing everything back to inStack after each pop works but makes every pop O(n).
    • Checking only one stack in empty. After a peek, all the values may be in outStack and inStack is empty, and the reverse is also common.
    • A fresh queue. empty() is True. After push(7) it is False, and after pop() returns 7 it is True again.
    • Interleaved operations. Pushing between pops is fine: the stale values in outStack leave first, and the new ones wait their turn.

    Testing

    q = MyQueue()
print(q.empty())
q.push(7)
print(q.empty(), q.pop(), q.empty())

    True
False 7 True
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free