Implement a Queue with Two Stacks

1. Problem Description

Use two stacks to implement a queue and complete the queue’s Push and Pop operations. The elements in the queue are of type int.

2. Approach

3. Implementation

• For a push operation, directly push into stack1. A pop operation is handled by cases: if stack2 is empty, transfer the data from stack1 to stack2, then pop from stack2; if stack2 is not empty, pop directly.

func stackPush(stack *[]int, data int) {
    *stack = append(*stack, data)
}

func stackPop(stack *[]int) int {
    if len(*stack) == 0 {return 0}
    data := (*stack)[len(*stack)-1]
    *stack = (*stack)[:len(*stack)-1]
    return data
}

func stackEmpty(stack *[]int) bool {
    return len(*stack) == 0
}

func stackPeek(stack *[]int) int {
    data := (*stack)[len(*stack)-1]
    return data
}

type MyQueue struct {
    pushStack []int
    popStack []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    stackPush(&this.pushStack, x)
}


func (this *MyQueue) Pop() int {
    if stackEmpty(&this.popStack) {
        for !stackEmpty(&this.pushStack) {
            data := stackPop(&this.pushStack)
            stackPush(&this.popStack, data)
        }
    }
    if !stackEmpty(&this.popStack) {
        return stackPop(&this.popStack)
    }
    return 0
}


func (this *MyQueue) Peek() int {
    if stackEmpty(&this.popStack) {
        for !stackEmpty(&this.pushStack) {
            data := stackPop(&this.pushStack)
            stackPush(&this.popStack, data)
        }
    }
    if !stackEmpty(&this.popStack) {
        return stackPeek(&this.popStack)
    }
    return 0
}


func (this *MyQueue) Empty() bool {
    return stackEmpty(&this.popStack) && stackEmpty(&this.pushStack)
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

4. References

• Implement a Queue with Two Stacks - NowCoder
• 232. Implement Queue using Stacks - LeetCode