leetcode 链接：225. 用队列实现栈

题目

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解答 & 代码

解法一：一个队列实现

入队操作前，先记录当前队列的 size，将当前元素入队，然后将前面的 size 个元素依次出队再入队
因此，push 的时间复杂度为 O(N)，其余操作的时间复杂度为 O(1)

  1. class MyStack {
  2. private:
  3.     queue<int> q;
  4. public:
  5.     /** Initialize your data structure here. */
  6.     MyStack() {
  7.     }
  9.     /** Push element x onto stack. */
  10.     void push(int x) {
  11.         int size = q.size();
  12.         q.push(x);    // 将当前元素插入队尾
  13.         // 将前面的元素依次出队再入队
  14.         for(int i = 0; i < size; ++i)
  15.         {
  16.             q.push(q.front());
  17.             q.pop();
  18.         }
  19.     }
  21.     /** Removes the element on top of the stack and returns that element. */
  22.     int pop() {
  23.         int top = q.front();
  24.         q.pop();
  25.         return top;
  26.     }
  28.     /** Get the top element. */
  29.     int top() {
  30.         return q.front();
  31.     }
  33.     /** Returns whether the stack is empty. */
  34.     bool empty() {
  35.         return q.size() == 0;
  36.     }
  37. };
  39. /**
  40.  * Your MyStack object will be instantiated and called as such:
  41.  * MyStack* obj = new MyStack();
  42.  * obj->push(x);
  43.  * int param_2 = obj->pop();
  44.  * int param_3 = obj->top();
  45.  * bool param_4 = obj->empty();
  46.  */

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.7 MB, 在所有 C++ 提交中击败了 45.05% 的用户