用两个栈实现队列

1. 题目描述

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

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

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. 代码