1. 题目描述

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

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

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())