Implement Queue using Stacks

easy stack queue design

Problem

Implement a FIFO queue using only two stacks. Support push, pop, peek, and empty.

Inputpush(1); push(2); peek(); pop();

Output1, 1

Push to in-stack. On pop/peek, if out-stack is empty, drain in → out so the FIFO order falls out.

ops (semicolon-separated)

class MyQueue:
    def __init__(self):
        self.in_s, self.out_s = [], []
    def push(self, x):
        self.in_s.append(x)
    def _shift(self):
        if not self.out_s:
            while self.in_s: self.out_s.append(self.in_s.pop())
    def pop(self):
        self._shift()
        return self.out_s.pop()
    def peek(self):
        self._shift()
        return self.out_s[-1]
    def empty(self):
        return not self.in_s and not self.out_s

class MyQueue {
  constructor() { this.inS = []; this.outS = []; }
  push(x) { this.inS.push(x); }
  _shift() { if (this.outS.length === 0) while (this.inS.length) this.outS.push(this.inS.pop()); }
  pop() { this._shift(); return this.outS.pop(); }
  peek() { this._shift(); return this.outS[this.outS.length - 1]; }
  empty() { return this.inS.length === 0 && this.outS.length === 0; }
}

class MyQueue {
    Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    public void push(int x) { in.push(x); }
    private void shift() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); }
    public int pop()  { shift(); return out.pop(); }
    public int peek() { shift(); return out.peek(); }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

class MyQueue {
    stack<int> inS, outS;
    void shift() { if (outS.empty()) while (!inS.empty()) { outS.push(inS.top()); inS.pop(); } }
public:
    void push(int x) { inS.push(x); }
    int pop()  { shift(); int v = outS.top(); outS.pop(); return v; }
    int peek() { shift(); return outS.top(); }
    bool empty() { return inS.empty() && outS.empty(); }
};

Explanation

A queue is first-in-first-out, but a stack is last-in-first-out — the opposite. The trick is that reversing twice gives back the original order, so two stacks together can act like one queue.

We keep an in stack and an out stack. Every push just goes onto in. The interesting part is pop/peek: if out is empty, we drain all of in into out one element at a time, which flips the order so the oldest element ends up on top of out.

After that flip, popping from out returns elements in true queue order. We only refill out when it runs empty, so each element moves between stacks at most once.

Example: push(1); push(2); peek(); pop();. After the two pushes in = [1,2]. The peek drains in into out = [2,1] (top is 1), so peek() = 1 and the following pop() also returns 1.

Because the expensive drain happens rarely, each operation costs amortized O(1).

Time: amortized O(1) per op Space: O(n)