栈和队列之间的转换

[heyushuo]

栈和队列

栈是后进先出(LIFO),队列是先进先出(FIFO),接下用两个队列去实现一个栈,主要实现 push 和 pop 操作,再用用两个栈实现一个队列,主要实现栈的 enqueue 和 dequeue.

如何用两个栈实现一个队列

解题思路

• 给两个栈分别命名 stack1,和 stack2,一个用来储存数据(stack1),一个用来操作(stack2).
• stack1 实现队列的 enqueue 方法,直接调用 push 方法把数据添加到栈中
• dequeue 方法是从队列的头部删除元素,然而此时 stack1 的的头部在栈的底部,是无法直接删除栈底的元素的
• 这个时候可以使用 stack2 了,把 stack1 的数据依次移除并压入 stack2 栈中,这样的话,stack2 的栈顶就变成队列的头部元素了,可以直接调用 stack2 的 pop 方法移除元素了
  当 stack1 和 stack2 都空的时候,队列中就没有元素了
  当 stack1 有元素,stack2 没有元素的时候,把 stack1 的数据移除压入 stack2 中

这里咱们直接用数组当成栈,不做封装

class Queue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  initStack() {
    var length1 = this.stack1.length;
    var length2 = this.stack2.length;
    if (length1 == 0 && length2 == 0) {
      //此时两个栈都是空的了
      return "";
    }
    //如果stack2是空的
    if (length2 == 0) {
      // 需要把stack1压栈到stack2中
      while (this.stack1.length != 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
  }
  // 向队尾添加一个元素
  enqueue(item) {
    this.stack1.push(item); // 把数据存入到stack1中
  }
  // 删除队首的一个元素
  dequeue() {
    //删除的先把stack1中的数据添加到stack2中
    this.initStack();
    return this.stack2.pop();
  }
}

var que = new Queue();
que.enqueue("a");
que.enqueue("b");
que.enqueue("c");
console.log(que); //Queue { stack1: [ 'a', 'b', 'c' ], stack2: [] }
que.dequeue();
console.log(que); //Queue { stack1: [], stack2: [ 'c', 'b' ] }

如何用两个队列实现一个栈

解题思路

• 给两个队列分别命名 queue1,和 queue2.
• queue1 实现栈的 push 方法,直接调用 push 方法把数据添加到栈中即可
• pop 方法是从栈的顶部删除元素,然而此时 queue1 的的顶部是无法直接删除的需要从队列头部开始删除
• 可以通过把 queue1 通过 dequeue 方法,把元素放入到 queue2,直到 queue1 队列中只剩一下一个元素,这个时候再把 queue2 中的元素全部放回 queue1 中,然后在执行 queue1 的 dequeue 方法即可把元素输出

class Stack {
  constructor() {
    //创建两个队列
    this.queue1 = [];
    this.queue2 = [];
  }
  initQueue() {
    //如果为空
    if (!this.queue2.length) {
      //把queue1中的放到queue2中最后只保留一个
      while (this.queue1.length != 1) {
        this.queue2.push(this.queue1.shift());
      }
      //然后再把队列2中的元素全部放回到1中
      while (this.queue2.length > 0) {
        this.queue1.push(this.queue2.shift());
      }
    }
  }
  push(item) {
    this.queue1.push(item);
  }
  pop() {
    this.initQueue();
    this.queue1.shift();
  }
}

var stac = new Stack();
stac.push("a");
stac.push("b");
stac.push("c");
console.log(stac); //Stack { queue1: [ 'a', 'b', 'c' ], queue2: [] }
stac.pop();
console.log(stac); //Stack { queue1: [ 'a', 'b' ], queue2: [] }