【算法题-简单】使用栈实现队列

简单算法题，使用栈模拟队列的功能，使用 JavaScript 语言编写

题目

使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

实现 MyQueue 类：

• push(number x): void 将元素 x 推到队列的末尾
• pop(): number 从队列的开头移除并返回元素
• peek(): number 返回队列开头的元素
• empty(): boolean 如果队列为空，返回 true，否则，返回 false

说明

• 只能使用标准的栈操作，即只有 push to top、peek/pop from top、size 和 is empty 操作是合法的
• 因为 JavaScript 中没有栈，需要自己实现栈 MinStack

输入格式

• 第一行输入是操作的序列，即 MinStack 类的方法名，以逗号分隔
• 第二行输入是成员函数所对应的参数，若没有参数则输入为 []

输出格式

输出为对应序列中每个操作的返回值

输入样例

push,push,peek,pop,empty
1,2,,,

输出样例

null,null,1,1,false

解释

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

分析

• 栈的特点是先进后出，队列的特点是先进先出
• JavaScript 中没有栈，需要自己实现栈 MinStack，可以使用数组来模拟栈

解答

// MinStack 类
class MinStack {
  constructor() {
    this.stack = [];
  }

  push(x) {
    // 进栈，放到栈的顶部
    this.stack.push(x);
  }

  pop() {
    // 出栈，从栈的顶部弹出元素
    return this.stack.pop();
  }

  peek() {
    // 栈的 peek 是取栈的顶部元素
    return this.stack[this.size() - 1];
  }

  size() {
    return this.stack.length;
  }

  empty() {
    return this.size() === 0;
  }
}

// MyQueue 类
class MyQueue {
  constructor() {
    this.in = new MinStack();
    this.out = new MinStack();
  }

  push(x) {
    // 入队
    this.in.push(x);
  }

  pop() {
    // 出队
    this.in2out();
    return this.out.pop();
  }

  peek() {
    // 取队首元素
    this.in2out();
    return this.out.peek();
  }

  empty() {
    return this.in.empty() && this.out.empty();
  }

  in2out() {
    // 将 in 转存到 out
    // 如果 out 为空，则一次性将 in 里面的元素全部转存到 out 里面，这样可以保证进队顺序不被打乱
    // 如果 out 不为空，则此时不能转存 in 里面的元素，不然顺序就乱了
    if (this.out.empty()) {
      while(this.in.size()) {
        this.out.push(this.in.pop());
      }
    }
  }
}

// 这是题目要求的输入格式
let inputs = `
  push,push,peek,pop,empty
  1,2,,,
`;

const [methodStr, parameterStr] = inputs.split('\n');
const methods = methodStr.split(',');
const parameters = parameterStr.split(',');
const outputs = [];
const myQueue = new MyQueue();

methods.forEach((method, idx) => {
  switch (method) {
    case 'push': {
      myQueue.push(parameters[idx]);
      outputs.push('null');
      break;
    }
    case 'peek':
    case 'pop':
    case 'empty': {
      outputs.push(myQueue[method]());
      break;
    }
  }
});

// 输出结果
console.log(outputs.join(','));