用栈实现队列

LeetCode 232 用栈实现队列 (JavaScript版😎)

题目描述

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

push(x) – 将一个元素放入队列的尾部。

pop() – 从队列首部移除元素。

peek() – 返回队列首部的元素。

iSEmpty() – 返回队列是否为空。

说明：

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

示例：

const queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

实现过程

/**
 * 初始化数据结构。
 */
function MyQueue(contents = []) {
  this.stack = [...contents];
  this.tempStack = [];
}

/**
 * 将元素 x 推入队列。
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.stack.push(x);
}

/**
 * 将队头元素推出，并返回该值。
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  let res;
  while (this.stack.length > 0) {
    this.tempStack.push(this.stack.pop());
  }
  res = this.tempStack.pop();

  // 由于上面的 stack 已经全部 pop 出到 tempStack,
  // 所以，需要在拿到目标值 res 后，将所有值重新推入 stack。
  while (this.tempStack.length > 0) {
    this.stack.push(this.tempStack.pop());
  }
  return res;
}

/**
 * 获取队头元素。
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  return this.stack[0];
}

/**
 * 判断列队是否为空。
 * @return {boolean}
 */
MyQueue.prototype.isEmpty = function () {
  return !this.stack.length;
}

/**
 * 获取队列长度。
 * @return {number}
 */
MyQueue.prototype.size = function () {
  return this.stack.length;
}

ES6 class 实现：

class MyQueue {
  constructor(contents = []) {
    this.stack = [...contents];
    this.tempStack = [];
  }
  push(x) {
    this.stack.push(x);
  }
  pop() {
    let res;
    while (this.stack.length > 0) {
      this.tempStack.push(this.stack.pop());
    }
    res = this.tempStack.pop();
    while (this.tempStack.length > 0) {
      this.stack.push(this.tempStack.pop());
    }
    return res;
  }
  peek() {
    return this.stack[0];
  }
  isEmpty() {
    return !this.stack.length;
  }
  size() {
    return this.stack.length;
  }
}

运行结果