Leetcode 225.用队列实现栈【C++】

地址：https://leetcode-cn.com/problems/implement-stack-using-queues/

题目

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

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意:

• 你只能使用队列的基本操作 – 也就是 push to back，peek/pop from front，size 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解题思路

使用C++标准模板库queue模板类实现。

• q.push(x)：将x插入到队列末端。
• q.pop()：弹出队列的第一个元素（不会返回被弹出元素的值）。
• q.front()：返回队首元素，即最早被压入队列的元素。
• q.empty()：判断队列是否为空，当队列空时，返回true。

插入元素x定义了一个临时队列 temp，然后将x插入到空的 temp 队列中，此时x是队首元素，即栈顶元素，然后将队列q（栈）中的所有元素依次取出并插入到temp队列的末端，此时得到的 temp 队列即将x入栈的得到的队列，然后再用同样的方法将 temp 队列的元素依次弹出并插入回队列q（栈）。

弹出栈顶元素即弹出队首元素，但需要返回弹出的队首元素值，而队列的 pop() 函数不会返回队首元素值，所以需要先定义一个临时 int 变量 temp 通过 front() 函数获取队首元素值，然后再弹出队首元素（即出栈），最后返回 temp 。

代码

class MyStack {
public:
    queue<int> q;
    
    /** Initialize your data structure here. */
    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> temp;
        temp.push(x);
        while(!q.empty()){
            temp.push(q.front());
            q.pop();
        }
        while(!temp.empty()){
            q.push(temp.front());
            temp.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int temp = q.front();
        q.pop();
        return temp;
    }
    
    /** Get the top element. */
    int top() {
        return q.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */