225. Implement Stack using Queues

Leetcode link

这个题目用 JS 做就没意义了，我只写了 C++ 的三个版本

解题思路——两个 queue，对 push 做手脚

push 操作时间复杂度：O(n)

维护两个队列，在 push 元素的时候首先把元素 push 到辅助队列 p2，然后把 p1 的元素逐个丢到 p2 ，最后把两个队列交换

C++

class MyStack {
private:
  queue<int> q1;
  queue<int> q2;

 public:
  MyStack() {}

  void push(int x) {
    q2.push(x);
    while (q1.size() > 0) {
      q2.push(q1.front());
      q1.pop();
    }
    swap(q1, q2);
  }

  int pop() {
    int res = q1.front();
    q1.pop();
    return res;
  }

  int top() { return q1.front(); }

  bool empty() { return q1.size() == 0; }
};

解题思路——两个 queue，对 pop 做手脚

pop 操作时间复杂度：O(n)

在做 pop 操作的时候，首先把队列 p1 除了最后一个元素之外都往 p2 丢，丢到最后一个元素的时候记得保存一下，然后先交换两个队列，最后再返回最后一个元素。

C++

class MyStack {
private:
  queue<int> q1;
  queue<int> q2;

 public:
  MyStack() {}

  void push(int x) {
    q1.push(x);
  }

  int pop() {
    // 除了最后一个元素之外其他都往 q2 丢
    while (q1.size() > 1) {
      q2.push(q1.front());
      q1.pop();
    }

    // 把最后一个元素保存一下
    int res = q1.front();
    q1.pop();

    // 把 q2 的元素丢回来
    while (q2.size() > 0) {
      q1.push(q2.front());
      q2.pop();
    }
    return res;
  }

  int top() {
      return q1.back();
  }

  bool empty() {
      return q1.size() == 0;
  }
};

解题思路—— 一个 queue

push 操作时间复杂度：O(n)

只有一个队列的时候情况有些不同了，考虑在 push 元素的时候，需要多出以下步骤

1. 先正常往队列尾部 push 元素
2. 把队列尾部之前的元素都从头部弹出之后插入尾部

这样以来，队列之后 pop 操作弹出的就是最后加进来的元素了

C++

class MyStack {
private:
  queue<int> q;

 public:
  MyStack() {}

  void push(int x) {
    q.push(x);
    int size = q.size();
    // 把最后一个元素以外的元素全部往队列尾部丢
    while (size > 1) {
      q.push(q.front());
      q.pop();
        size--;
    }
  }

  int pop() {
    int res = q.front();
    q.pop();
    return res;
  }

  int top() { return q.front(); }

  bool empty() { return q.size() == 0; }
};