用两个栈实现队列

发表于 | 分类于 |
字数统计: 615 字 | 阅读时长 ≈ 2 分钟

题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CQueue {

  public CQueue() {

  }

  public void appendTail(int value) {

  }

  public int deleteHead() {

  }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

方法一：双栈

利用栈先进后出的特点，维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作。

插入不多说；删除时，首先判断 stack2 有无元素，无则将 stack1 的元素一个个弹出插入到栈里，这么一来，stack1 的头结点便在 stack2 的尾结点处，即 stack2 里元素的顺序就是待删除的元素的顺序。执行删除操作时，直接弹出 stack2 的元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class CQueue {
  Deque<Integer> stack1, stack2;
  public CQueue() {
    stack1 = new LinkedList<Integer>();
    stack2 = new LinkedList<Integer>();
  }

  public void appendTail(int value) {
    stack1.push(value);
  }

  public int deleteHead() {
    if(stack2.isEmpty()){
      while(!stack1.isEmpty()) {
        stack2.push(stack1.pop());
      }
    }
    return stack2.isEmpty() ? -1 : stack2.pop();
  }
}
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
var CQueue = function() {
  this.stack1 = [], this.stack2 = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
  this.stack1.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
  if(!this.stack2.length) {
    if(!this.stack1.length) return -1;
    while(this.stack1.length) {
      this.stack2.push(this.stack1.pop());
    }
  }
  return this.stack2.pop();
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

复杂度分析：

  • 时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)

  • 空间复杂度：O(n)。需要使用两个栈存储已有的元素

执行结果：通过

  • 执行用时：43 ms, 在所有 Java 提交中击败了96.13%的用户

    内存消耗：47 MB, 在所有 Java 提交中击败了32.87%的用户