栈和队列的相互实现

栈实现队列

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例:

let queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

来源: LeetCode第232题

思路

既然栈是先进后出, 要想得到先进先出的效果，我们不妨用两个栈。

当进行push操作时，push 到 stack1，而进行pop和peek的操作时，我们通过stack2。

当然这其中有一个特殊情况，就是stack2是空，如何来进行pop和peek? 很简单，把stack1中的元素依次 pop 并推入stack2中，然后正常地操作 stack2即可，如下图所示:

这就就能保证先入先出的效果了。

代码实现

var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};
// 将 stack1 的元素转移到 stack2
MyQueue.prototype.transform = function() {
  while(this.stack1.length) {
    this.stack2.push(this.stack1.pop());
  }
}

MyQueue.prototype.pop = function() {
  if(!this.stack2.length) this.transform();
  return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
    if(!this.stack2.length) this.transform();
    return this.stack2[this.stack2.length - 1];
};

MyQueue.prototype.empty = function() {
    return !this.stack1.length && !this.stack2.length;
};

队列实现栈

和上一题的效果刚好相反，用队列先进先出的方式来实现先进后出的效果。

思路

以上面的队列为例，push 操作好说，直接从在队列末尾推入。但 pop 和 peek 呢？

回到我们的目标，我们的目标是拿到队尾的值，也就是3。这就好办了，我们让前面的元素统统出队，只留队尾元素即可，剩下的元素让另外一个队列保存。

来源: LeetCode第225题

代码实现

实现过程中，值得注意的一点是，queue1 始终保存前面的元素，queue2 始终保存队尾元素（即栈顶元素 ）。

但是当 push 的时候有一个陷阱，就是当queue2已经有元素的时候，不能将新值 push 到 queue1，因为此时的栈顶元素应该更新。此时对于新的值来说，应先 push 到 queue2， 然后将旧的栈顶从queue2出队，推入 queue1，这样就实现了更新栈顶的操作。

var MyStack = function() {
    this.queue1 = [];
    this.queue2 = [];
};
MyStack.prototype.push = function(x) {
    if(!this.queue2.length) this.queue1.push(x);
    else {
        // queue2 已经有值
        this.queue2.push(x);
        // 旧的栈顶移到 queue1 中
        this.queue1.push(this.queue2.shift());
    }

};
MyStack.prototype.transform = function() {
    while(this.queue1.length !== 1) {
        this.queue2.push(this.queue1.shift())
    }
    // queue2 保存了前面的元素
    // 让 queue1 和 queue2 交换
    // 现在queue1 包含前面的元素，queue2 里面就只包含队尾的元素
    let tmp = this.queue1;
    this.queue1 = this.queue2;
    this.queue2 = tmp;
}
MyStack.prototype.pop = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2.shift();
};
MyStack.prototype.top = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2[0];
};
MyStack.prototype.empty = function() {
    return !this.queue1.length && !this.queue2.length;
};

---

Last update: May 28, 2021