用栈实现队列

题目

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

type MyQueue struct {

}


/** Initialize your data structure here. */
func Constructor() MyQueue {

}


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {

}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {

}


/** Get the front element. */
func (this *MyQueue) Peek() int {

}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {

}


/**
 * 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();
 */

思路

用两个栈，一个负责push，一个负责pop，实际上是借助slice实现栈

流程：

  • 入栈：直接推到 push栈
  • 出栈：
    • 检查 pop栈是否有元素
      • 有：出栈
      • 没有：push栈全部推到 pop 栈，再出栈

注意：如果pop栈空，不能直接 push[0]，因为栈不能直接取栈底元素

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

type MyQueue struct {
    pushStk []int
    popStk  []int
}


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


/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int)  {
    this.pushStk = append(this.pushStk, x)
}


/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
    
    // if len(this.popStk) == 0 {
    //     // 出栈过程
    //     for len(this.pushStk) > 0 {
    //         this.popStk = append(this.popStk, this.pushStk[len(this.pushStk)-1])
    //         this.pushStk = this.pushStk[:len(this.pushStk)-1]
    //     }
    // }
    defer func () {
        this.popStk = this.popStk[:len(this.popStk)-1]
    }()
    return this.Peek()
}


/** Get the front element. */
func (this *MyQueue) Peek() int {
    if len(this.popStk) == 0 {
        // 出栈过程
        for len(this.pushStk) > 0 {
            this.popStk = append(this.popStk, this.pushStk[len(this.pushStk)-1])
            this.pushStk = this.pushStk[:len(this.pushStk)-1]
        }
    }
    return this.popStk[len(this.popStk)-1]
}


/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
    return len(this.popStk)==0 && len(this.pushStk)==0
}


/**
 * 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();
 */

// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2 MB, 在所有 Go 提交中击败了61.90%的用户

能省的空间都省了，每次提交结果都不一样，就这样吧