题目描述

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

  • push(x) – 将一个元素放入队列的尾部。
  • pop() – 从队列首部移除元素。
  • peek() – 返回队列首部的元素。
  • empty() – 返回队列是否为空。

思路

创建两个栈 s1， s2

  1. 入队

    将元素放入 s1 中

  2. 出队

    • 若 s2 为空，将 s1 的元素 放入 s2 中， 此时 s2 的栈顶就是队首元素，s2 栈顶出栈。
    • 若 s2 不为空，直接将 s2 栈顶元素出栈即可。

  3. 获取队首元素

    • 若 s2 不为空，s2 的栈顶元素就是队首元素。
    • 若 s2 为空，s1 不为空，将 s1 中的元素放入 s2 中，然后 s2 的栈顶元素就是队首元素。 
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1, s2;
    int temp;
    int res;
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                temp = s1.top();
                s2.push(temp);
                s1.pop();
            }
            res = s2.top();
            s2.pop();
            return res;
        }
        else
        {
            res = s2.top();
            s2.pop();
            return res;
        }
    }

    /** Get the front element. */
    int peek() {
        if(!s2.empty())
        {
            res = s2.top();
            return res;
        }
        else if(!s1.empty())
        {
            while(!s1.empty())
            {
                temp = s1.top();
                s2.push(temp);
                s1.pop();
            }
            res = s2.top();
            return res;
        }
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};