Implement Queue Using Stacks

class MyQueue {
    stack<int> in, out;
    void shift() {
        if (out.empty())
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }

    int pop() {
        shift();
        int v = out.top(); out.pop();
        return v;
    }

    int peek() {
        shift();
        return out.top();
    }

    bool empty() { return in.empty() && out.empty(); }
};

type MyQueue struct {
    in, out []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (q *MyQueue) shift() {
    if len(q.out) == 0 {
        for len(q.in) > 0 {
            n := len(q.in)
            q.out = append(q.out, q.in[n-1])
            q.in = q.in[:n-1]
        }
    }
}

func (q *MyQueue) Push(x int) {
    q.in = append(q.in, x)
}

func (q *MyQueue) Pop() int {
    q.shift()
    n := len(q.out)
    v := q.out[n-1]
    q.out = q.out[:n-1]
    return v
}

func (q *MyQueue) Peek() int {
    q.shift()
    return q.out[len(q.out)-1]
}

func (q *MyQueue) Empty() bool {
    return len(q.in) == 0 && len(q.out) == 0
}

class MyQueue:
    def __init__(self):
        self.in_stk: list = []
        self.out_stk: list = []

    def _shift(self) -> None:
        if not self.out_stk:
            while self.in_stk:
                self.out_stk.append(self.in_stk.pop())

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

    def pop(self) -> int:
        self._shift()
        return self.out_stk.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_stk[-1]

    def empty(self) -> bool:
        return not self.in_stk and not self.out_stk

class MyQueue {
    constructor() {
        this.inStk = [];
        this.outStk = [];
    }

    _shift() {
        if (this.outStk.length === 0) {
            while (this.inStk.length > 0) {
                this.outStk.push(this.inStk.pop());
            }
        }
    }

    push(x) {
        this.inStk.push(x);
    }

    pop() {
        this._shift();
        return this.outStk.pop();
    }

    peek() {
        this._shift();
        return this.outStk[this.outStk.length - 1];
    }

    empty() {
        return this.inStk.length === 0 && this.outStk.length === 0;
    }
}

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>();
    private Deque<Integer> out = new ArrayDeque<>();

    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

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

    public int pop() {
        shift();
        return out.pop();
    }

    public int peek() {
        shift();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

class MyQueue {
    private inStk: number[] = [];
    private outStk: number[] = [];

    private shift(): void {
        if (this.outStk.length === 0) {
            while (this.inStk.length > 0) {
                this.outStk.push(this.inStk.pop()!);
            }
        }
    }

    push(x: number): void {
        this.inStk.push(x);
    }

    pop(): number {
        this.shift();
        return this.outStk.pop()!;
    }

    peek(): number {
        this.shift();
        return this.outStk[this.outStk.length - 1];
    }

    empty(): boolean {
        return this.inStk.length === 0 && this.outStk.length === 0;
    }
}