Queue Using Two Stacks

Medium

Python

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

Java

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

Key Insight

Two-stack queue. out[-1] vs peek(). list as stack.

Python → Java Differences

list as stack vs Stack class
out[-1] vs peek()
Two-stack queue identical

Python

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

Java

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

Algorithm Steps

1. Push to in-stack
2. Transfer when out empty
3. Pop from out

← Previous All Stacks & Queues Next →