1. 题目描述

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

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

2. 解题思路

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

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

3. 代码

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