1. 题目描述

用两个栈实现一个队列。队列的声明如下:

请实现它的两个函数appendTaildeleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

2. 解题思路

一个栈用来存储插入队列数据,一个栈用来从队列中取出数据。

从第一个栈向第二个栈转移数据的过程中:数据的性质已经从后入先出变成了先入先出。

3. 代码

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
class Queue {
constructor() {
this.stack1 = []
this.stack2 = []
}

appendTail(value) {
// 新插入队列的数据都放在 stack1
this.stack1.splice(0, 0, value)
}

deleteHead() {
// 将要取出的值都从stack2中取
// 如果stack2为空,那么将 stack1 中的元素都转移过来
// 此时,stack2中的元素顺序已经被改变了,满足队列的条件
if (this.stack2.length === 0) {
let length = this.stack1.length
for (let i = 0; i < length; ++i) {
this.stack2.splice(0, 0, this.stack1.shift())
}
}

return this.stack2.length === 0 ? null : this.stack2.shift()
}
}

/**
* 测试代码
*/

let queue = new Queue()
queue.appendTail(1)
queue.appendTail(2)
queue.appendTail(3)

console.log(queue.deleteHead())
queue.appendTail(1)

console.log(queue.deleteHead())
console.log(queue.deleteHead())
console.log(queue.deleteHead())