225.用队列实现栈

一、问题描述

实现一个栈，该栈使用两个队列作为内部存储结构。栈的主要操作包括：

• push(x)：将元素 x 推入栈顶。
• pop()：移除栈顶元素。
• top()：返回栈顶元素。
• empty()：检查栈是否为空。

二、方案一：使用一个队列

1、思路

设计思路：队首变成最后一个加入的元素

push 操作：将元素加入到队列中

top 操作：将队列中的前 n-1 个元素出队并重新加入队列

2、代码实现

type MyStack struct {
    queue []int
}
func Constructor() MyStack {
    return MyStack{}
}
func (this *MyStack) Push(x int) {
    this.queue = append(this.queue, x)
}
func (this *MyStack) Pop() int {
    n := len(this.queue)
    // 将队列中的前 n-1 个元素出队并重新加入队列
    for i := 0; i < n-1; i++ {
        this.queue = append(this.queue, this.queue[0])
        this.queue = this.queue[1:]
    }
    // 队首变成最后一个加入的元素
    top := this.queue[0]
    this.queue = this.queue[1:]
    return top
}
func (this *MyStack) Top() int {
    top := this.Pop()
    this.Push(top)
    return top
}
func (this *MyStack) Empty() bool {
    return len(this.queue) == 0
}

3、复杂度分析

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

三、方案二：使用两个队列

1、思路

设计思路：队列 1 用于存储元素，进行入队列和出队列；队列 2 用于纯辅助操作

push 操作：将元素加入到队列 1

pop 操作：将队列 1 的前 n - 1 个元素转移到 辅助队列2 中，然后移除剩下的一个元素，然后交换 队列1 和 队列 2

2、代码实现

Pop 操作使用辅助队列

type MyStack struct {
    queue1, queue2 []int
}
func Constructor() MyStack {
    return MyStack{}
}
func (this *MyStack) Push(x int) {
    this.queue1 = append(this.queue1, x)
}
func (this *MyStack) Pop() int {
	// 将队列 1 的前 n - 1 个元素转移到 辅助队列2 
    for len(this.queue1) > 1 {
        this.queue2 = append(this.queue2, this.queue1[0])
        this.queue1 = this.queue1[1:]
    }
    top := this.queue1[0]
    // 移除剩下的一个元素
    this.queue1 = this.queue1[1:]
    // 交换 队列1 和 队列 2
    this.queue1, this.queue2 = this.queue2, this.queue1
    return top
}
func (this *MyStack) Top() int {
    top := this.Pop()
    this.queue1 = append(this.queue1, top)
    return top
}
func (this *MyStack) Empty() bool {
    return len(this.queue1) == 0
}

Push 操作使用辅助队列

type MyStack struct {
    queue1, queue2 []int
}

/** Initialize your data structure here. */
func Constructor() (s MyStack) {
    return
}

/** Push element x onto stack. */
func (s *MyStack) Push(x int) {
    s.queue2 = append(s.queue2, x)
    for len(s.queue1) > 0 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    s.queue1, s.queue2 = s.queue2, s.queue1
}

/** Removes the element on top of the stack and returns that element. */
func (s *MyStack) Pop() int {
    v := s.queue1[0]
    s.queue1 = s.queue1[1:]
    return v
}

/** Get the top element. */
func (s *MyStack) Top() int {
    return s.queue1[0]
}

/** Returns whether the stack is empty. */
func (s *MyStack) Empty() bool {
    return len(s.queue1) == 0
}

3、复杂度分析

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

四、总结

虽然使用两个队列在 pop 和 top 操作时稍微优化了时间复杂性，但总体来说，两种方法的时间复杂性相似。选择哪种方法取决于具体的应用场景和性能需求。在大多数情况下，使用一个队列的方法因为更简单而更受欢迎。