Implement Queue Using Stacks

+10

Build a first in, first out queue whose only storage is two stacks. A stack may only add an item on top, remove the top item, read the top item and tell whether it is empty. The queue supports push x (add x at the back), pop (remove and return the front item), peek (return the front item) and empty (is the queue empty?).

You get the operations in order as ops, with args[i] holding the value for a push and 0 for every other operation. Run them on one queue that starts empty and return one string per operation: "null" for a push, the number as text for a pop or a peek, and "true" or "false" for empty.

Function

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: the operations, in the order they run
argsinteger-array: the value for each push, 0 for every other operation
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ ops.length ≤ 2000
args.length == ops.length
Every ops[i] is push, pop, peek or empty.
-10⁹ ≤ args[i] ≤ 10⁹ for a push, and args[i] == 0 for any other operation.
pop and peek are only called when the queue holds at least one item.

Examples

Input: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Output: ["null", "null", "1", "1", "false"]
Explanation: After pushing 1 and then 2, the front is 1, so peek and pop both return "1". The 2 is still inside, so empty returns "false".

Input: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Output: ["null", "null", "4", "null", "7", "9", "true"]
Explanation: The first pop returns 4, the oldest item. 9 arrives while 7 is still waiting, and it comes out after 7 because it came in after it. The queue is then empty, so the last answer is "true".

Input: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Output: ["true", "null", "-3", "-3", "true"]
Explanation: The queue starts empty, so the first answer is "true". A negative number is stored like any other: peek and pop both return "-3", and then the queue is empty again.

+15 hidden tests on Submit

Follow-up

How would you add a back operation that returns the newest item in O(1), without breaking the amortized bound of the others?

Solution

A stack gives items back in the reverse order they arrived, and a queue in the same order. Pouring a stack into a second stack reverses it once more, which turns stack order into queue order. The whole question is when to pour: doing it on every operation costs O(n) each time, while pouring only when the second stack runs dry moves each item across only once.

Reorder the whole stack on every push

Intuition

Keep every item in one stack, main, arranged so the oldest item sits on top. Then pop, peek and empty are single stack operations.

The work moves to push. A new item belongs at the bottom, under everything already waiting, and a stack can only add on top. So move every item from main onto the second stack, helper, push the new item onto the empty main, and move everything back. Each move reverses the order, two moves restore it, and the new item ends up underneath.

This is correct, but each push touches every stored item twice. Pushing 1,000 items in a row costs about 2 × (0 + 1 + ... + 999), close to a million moves, where a real queue needs 1,000 steps.

Algorithm

Keep two stacks, main with the oldest item on top, and an empty helper.
For push x: pop every item from main onto helper, push x onto main, then pop every item from helper back onto main.
For pop and peek: pop or read the top of main.
For empty: report whether main is empty.
Record each answer as text and return the list.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Inbox and outbox stacks with lazy transfer

Intuition

Give the stacks separate jobs. Every push goes onto inbox, in O(1). Pops and peeks read from outbox, whose top is always the oldest item in the queue.

When outbox is empty and a pop or peek arrives, pour all of inbox into it. The newest item comes off inbox first, so it lands at the bottom of outbox, and the oldest lands on top. Pour only when outbox is empty: while it still holds items, they are older than anything in inbox, so they must leave first. In the second example, 4 and 7 are poured over for the first pop; 9 then waits in inbox until 7 has left.

A single pop can move many items, but count the work per item instead: each value is pushed onto inbox once, moved to outbox once and popped once. n operations therefore cost O(n) in total, which is O(1) amortized per operation. The queue is empty when both stacks are empty.

Algorithm

Keep two empty stacks, inbox and outbox.
For push x: push x onto inbox.
For pop or peek: if outbox is empty, pop every item of inbox onto outbox. Then pop or read the top of outbox.
For empty: report whether both stacks are empty.
Record each answer as text and return the list.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Pitfalls and edge cases

Most bugs come from pouring at the wrong moment or from checking only one stack.

Pouring inbox into outbox while outbox still holds items. The new items land on top of older ones and leave first, which breaks the queue order. In the second example, 9 would come out before 7.
Reporting empty from outbox alone. Right after a push the new item sits in inbox, so the queue is not empty even though outbox is.
Forgetting that peek needs the same refill as pop. A peek right after the first pushes finds outbox empty.
Using a library queue or reading the bottom of a stack by index. The point is to get queue order out of stack operations only.
Returning numbers or booleans instead of text. Every answer is a string, including "null" for a push.

Frequently asked questions4

What is the time complexity of a queue built from two stacks?

Push is O(1). Pop and peek are O(1) amortized: one call can move every item from one stack to the other, but each item is moved at most once in its life, so n operations cost O(n) in total. The two stacks together hold each item once, so the space is O(n).

What does amortized O(1) mean here?

It means the average cost per operation over the whole sequence is constant, even though a single operation can be slow. A pop that pours 1,000 items is paid for by the 1,000 cheap pushes before it, because those items will never be poured again. No sequence of n operations costs more than about 4n stack steps.

Why do you need two stacks and not one?

A single stack only exposes its newest item, and a queue needs its oldest. Reaching the bottom of one stack means removing everything above it, and those items need somewhere to wait, which is the second stack. Moving items across reverses their order, and that reversal is what turns newest first into oldest first.

Can you implement a stack using queues instead?

Yes, but the usual ways give no amortized saving. A common one uses one queue: after adding a new item, take each older item from the front and add it to the back, so the new item ends up at the front. That makes push O(n) and pop O(1).

Python

def queueOps(ops, args):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

Expected

["null", "null", "1", "1", "false"]