Chipmunk & Panda

-- 鼠熊部落格

All work and no play makes Jack a dull boy.

用两个栈实现队列

  数据结构与算法     

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

初见

采用正向栈和反向栈，同一时间两个栈只有一个有内容，存储队列中全部元素。

队列 = 正向栈栈底 -> 正向栈栈顶

或

队列 = 反向栈栈顶 -> 反向栈栈底

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
var CQueue = function () {
  this.stack = [] // 正向栈，队首在栈底，队尾在栈顶，即当队列为 [3, 4, 5] 时栈内存储为 [3, 4, 5]
  this.stack_reversed = [] // 反向栈，队尾在栈底，队首在栈顶，即当队列为 [3, 4, 5] 时栈内存储为 [5, 4, 3]
  this.reversed = false // 表示队列当前存储在正向栈还是反向栈中
}

// 在队尾添加元素
CQueue.prototype.appendTail = function (value) {
  // 存储在反向栈时，需要先把队列转移进正向栈
  if (this.reversed) {
    let len = this.stack_reversed.length
    for (let i = 0; i < len; i++) {
      this.stack.push(this.stack_reversed.pop())
    }
    this.reversed = !this.reversed
  }
  this.stack.push(value) // 将新元素添加在正向栈栈顶
}

// 删除队首元素
CQueue.prototype.deleteHead = function () {
  // 队列为空时返回 -1
  if (this.stack.length === 0 && this.stack_reversed.length === 0) {
    return -1
  }

  // 存储在正向栈时，需要先把队列转移进反向栈，正向栈栈底元素即队首元素，直接删除
  if (!this.reversed) {
    let len = this.stack.length
    for (let i = 1; i < len; i++) {
      this.stack_reversed.push(this.stack.pop())
    }
    value = this.stack.pop()
    this.reversed = !this.reversed
    return value
  }
  // 存储在反向栈时，反向栈栈顶元素即队首元素，直接删除
  else {
    return this.stack_reversed.pop()
  }
}

// 测试用例
var obj = new CQueue()
obj.appendTail(3)
obj.appendTail(4)
console.log(obj.deleteHead()) // 3
console.log(obj.deleteHead()) // 4
obj.appendTail(5)
console.log(obj.deleteHead()) // 5
console.log(obj.deleteHead()) // -1

优解

两个栈，一个负责入队，一个负责出队。出队时若出队栈非空则直接出队，否则一次性将入队栈已有内容全部转移入出队栈，这样就不用反复在两个栈之间来回倒腾队列元素了。

队列 = 出队栈栈顶 -> 出队栈栈底 -> 入队栈栈顶 -> 入队栈栈底。

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
var CQueue = function () {
  this.stack_in = [] // 负责入队
  this.stack_out = [] // 负责出队
}

// 在队尾添加元素
CQueue.prototype.appendTail = function (value) {
  this.stack_in.push(value)
}

// 删除队首元素
CQueue.prototype.deleteHead = function () {
  if (this.stack_out.length === 0) {
    if (this.stack_in.length === 0) {
      return -1
    }

    while (this.stack_in.length > 1) {
      this.stack_out.push(this.stack_in.pop())
    }

    return this.stack_in.pop()
  }

  return this.stack_out.pop()
}