一、问题描述

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

二、方案一：使用两个栈

1、思路

我们可以使用两个栈来实现队列。一个栈用于插入元素，另一个栈用于删除元素。当我们需要删除元素时，如果第二个栈为空，则将第一个栈的所有元素移动到第二个栈中，这样第二个栈的顶部就是队列的头部。

栈先入后出的特性导致不能在 push 时使用辅助，因为倒腾一次数据，并不能保持数据的单调性，所以在 pop 时使用

2、代码实现

type MyQueue struct {
    inStack, outStack []int
}
func Constructor() MyQueue {
    return MyQueue{}
}
func (this *MyQueue) Push(x int) {
    this.inStack = append(this.inStack, x)
}
func (this *MyQueue) Pop() int {
    this.peek()
    top := this.outStack[len(this.outStack)-1]
    this.outStack = this.outStack[:len(this.outStack)-1]
    return top
}
func (this *MyQueue) Peek() int {
    if len(this.outStack) == 0 {
        for len(this.inStack) > 0 {
            this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
            this.inStack = this.inStack[:len(this.inStack)-1]
        }
    }
    return this.outStack[len(this.outStack)-1]
}
func (this *MyQueue) Empty() bool {
    return len(this.inStack) == 0 && len(this.outStack) == 0
}

3、复杂度分析

• 时间复杂度：Push 和 Pop 在最坏情况下是 O(n)，但均摊下来是 O(1)。
• 空间复杂度：O(n)，因为我们需要额外的空间来存储两个栈中的元素。

三、方案二：使用一个栈

1、思路

我们也可以只使用一个栈来实现队列。每次插入元素时，如果栈不为空，我们需要将栈中的所有元素弹出并存储在另一个临时栈中，然后将新元素插入栈底，最后将临时栈中的元素再放回原栈。

2次倒腾，栈中的数据保持先入后出

2、代码实现

type MyQueue struct {
    stack []int
}
func Constructor() MyQueue {
    return MyQueue{}
}
func (this *MyQueue) Push(x int) {
    tempStack := []int{}
    for len(this.stack) > 0 {
        tempStack = append(tempStack, this.stack[len(this.stack)-1])
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = append(this.stack, x)
    for len(tempStack) > 0 {
        this.stack = append(this.stack, tempStack[len(tempStack)-1])
        tempStack = tempStack[:len(tempStack)-1]
    }
}
func (this *MyQueue) Pop() int {
    top := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    return top
}
func (this *MyQueue) Peek() int {
    return this.stack[len(this.stack)-1]
}
func (this *MyQueue) Empty() bool {
    return len(this.stack) == 0
}

3、复杂度分析

• 时间复杂度：Push 是 O(n)，Pop 和 Peek 是 O(1)。
• 空间复杂度：O(n)，因为我们需要额外的空间来存储临时栈中的元素。

四、总结

方案	时间复杂度	空间复杂度	备注
使用两个栈	均摊 O(1)	O(n)	更优的均摊时间复杂度
使用一个栈	O(n)	O(n)	简单但时间复杂度较高

推荐使用两个栈的方案，因为它有更优的均摊时间复杂度。