JavaScript数据结构之队列和栈双手互搏

菜小编

2018-12-28

WEB前端开发

学习了队列和栈以后，今天就可以试着来用两个栈实现队列的功能或者用两个队列来实现栈的功能。

数据结构之---栈实现队列

1. 用两个栈实现一个队列

1.1 题目分析

栈是先进后出，队列是先进先出，但可以用两个栈来模拟一个队列的功能，来实现队列中主要的enqueue，dequeue， head 方法。

1.2 思路分析

我们所学的每一种数据结构，本质上都是对数据如何存储和使用的研究，这就必然涉及到增删改查，那么考虑实现这些方法时，我们优先考虑如何实现数据的增加，只有存在了数据，才能够后续的操作。所以如何实现队列中的增加数据方法enqueue呢？

给两个栈分别命名为 stack1，stack2。那有了这两个栈以后，可以选取其中一个来存储数据，比如说stack1，那么队列的enqueue方法就很容易了，直接利用栈的push方法就能够添加数据。

接下来考虑队列中的删除dequeue方法

首先要注意下dequeue方法是删除队列中的头部元素，而此时队首是在stack1栈底的，目前来说还取不到。

这个时候stack2该上场了，可以把stack1中的元素都依次移除并压入stack2中，这样的话，stack2的栈顶就变成了队首，不就可以利用stack2的pop方法来移除元素了嘛。

那队列的head方法呢

执行完stack2的pop方法后，还需要把数据再移回stack1里吗？其实不需要了，因为此时队首正好是stack2的栈顶，而队列的head方法就可以利用栈的top方法来实现了。

如果stack2是空的怎么办？那stack1的元素都移除到stack2就可以了。

如果stack1也是空的呢，那就说明队列中没有元素了，此时返回null就可以了。

注意到了吗，这里又用到了***分而治之*** 的思想，还记得之前在哪里用过吗？对，就是在给栈添加获取最小值方法的时候用过，当时也是用了两个栈来实现。这里的话enqueue始终都操作stack1，dequeue和head方法始终都操作stack2。

1.3 代码实现

{
        class StackQueue {
          constructor() {
            this.stack1 = new Stack();
            this.stack2 = new Stack();
          }
          // 初始化stack，伪造私有方法
          _initStack() {
            if (this.stack1.isEmpty() && this.stack2.isEmpty()) {
              return null; // 如果两个栈都是空的，那么队列中就没有元素
            }
            if (this.stack2.isEmpty()) {
              // 如果stack2是空的，那么此时stack1一定不为空
              while (!this.stack1.isEmpty()) {
                this.stack2.push(this.stack1.pop()); // 把stack1的元素移除到stack2中
              }
            }
          }
          // 向队尾添加一个元素
          enqueue(item) {
            this.stack1.push(item); // 把数据存入到stack1中
          }
          // 删除队首的一个元素
          dequeue() {
            this._initStack();
            return this.stack2.pop();
          }
          // 返回队首的元素
          head() {
            this._initStack();
            return this.stack2.top();
          }
        }
        var stackQueue = new StackQueue();
        stackQueue.enqueue(1);
        stackQueue.enqueue(4);
        stackQueue.enqueue(8);
        console.log(stackQueue.head()); // 1
        stackQueue.dequeue();
        stackQueue.enqueue(9);
        console.log(stackQueue.head()); // 4
        stackQueue.dequeue();
        console.log(stackQueue.head()); // 8
        console.log(stackQueue.dequeue()); // 8
        console.log(stackQueue.dequeue()); // 9
      }
复制代码

是不是觉得很简单呢，梳理清楚队列和栈的特性就OK啦。接下来让我们继续修炼，用队列实现栈吧！

2. 用两个队列实现一个栈

2.1 题目分析

队列是先进先出，栈是先进后出，(不断重复这两个知识点) 但可以用两个队列来模拟一个栈的功能，来实现栈中主要的push，pop， top 方法。

你可能会想到利用上边的套路来实现这个需求，但是最后的结果你会发现是不正确的。因为把stack1的元素移除到stack2中，此时的两个栈中的数据就首尾交换了，而如果此处换成队列 this.queue2. enqueue(this.queue1. dequeue())，你会发现由于队列的特性，此时的两个队列还是一样的，首尾并没有交换。

so 我们来换个思路

2.2 思路分析

和上边一样，我们先考虑如何实现栈的存储数据push方法:

给两个队列分别命名为 queue1，queue2。实现push方法时，利用队列的enqueue方法，如果两个队列都为空，那么默认向queue1里添加数据；如果有一个不为空，那么就向这个不为空的队列里添加数据。

top方法就简单了:

利用队列的tail方法，两个队列要么都为空，要么有一个不为空，那么返回不为空队列的尾部元素就是栈顶元素了.

接下来思考比较复杂的pop方法:

pop方法删除的是栈顶，但此时栈顶元素是队列的尾部元素，而队尾元素是不能删除的。

但每次执行pop时，可以将不为空的a队列里的元素循环删除并放入到另一个b队列中，直到a队列中只剩下一个元素，此时a队列的这个元素就是队列的尾部元素，也就是栈顶元素了，那pop方法就简单了，利用a队列的dequeue方法就可以了。

在具体的实现中，需要额外定义两个变量，dataQueue和emptyQueue:

dataQueue始终指向那个不为空的队列

emptyQueue始终指向那个为空的队列

2.3 代码实现

  {
      class QueueStack {
        constructor() {
          this.queue1 = new Queue();
          this.queue2 = new Queue();
          this.dataQueue = null; // 存放数据的队列
          this.emptyQueue = null; // 存放备份数据的队列
        }
        // 初始化队列数据，模拟私有方法 确认哪个队列存放数据，哪个队列做备份 
        _initQueue() {
          if (this.queue1.isEmpty()) {
            this.dataQueue = this.queue2;
            this.emptyQueue = this.queue1;
          } else {
            // 都为空的话 默认是 队列1
            this.dataQueue = this.queue1;
            this.emptyQueue = this.queue2;
          }
        }
        // 往栈里压入一个元素
        push(item) {
          this._initQueue();
          this.dataQueue.enqueue(item);
        }
        // 返回栈顶的元素
        top() {
          this._initQueue();
          return this.dataQueue.tail();
        }
        // 把栈顶的元素移除
        pop() {
          this._initQueue();
          while (this.dataQueue.size() > 1) {
            // 利用备份队列转移数据，
            this.emptyQueue.enqueue(this.dataQueue.dequeue()); // 数据队列和备份队列交换了身份
          }
          return this.dataQueue.dequeue(); // 移除数据队列的头部元素
        }
      }
      var queueStack = new QueueStack();
      queueStack.push(1);
      queueStack.push(2);
      queueStack.push(4);
      console.log(queueStack.top()); // 栈顶是 4
      console.log(queueStack.pop()); // 移除 4
      queueStack.push(5);
      console.log(queueStack.top()); // 栈顶变成 5
      queueStack.push(6);
      console.log(queueStack.pop()); // 移除 6
      console.log(queueStack.pop()); // 移除5
      console.log(queueStack.top()); // 栈顶是 2
    }
复制代码