题解43 | 好吧其实一个也行#两个队列实现栈#

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param order string字符串vector 
     * @return string字符串vector
     */
    queue<int>q1;//一个队列也能实现栈
    queue<int>q2;//q2:???你创立我干嘛

    void push(int element){
        q1.push(element);
    } //等价于将元素 element 压入栈顶。

    int pop(){
        int s = q1.size();
        s--;
        while (s--) {
            q1.push(q1.front());
            q1.pop();
        }
        int f = q1.front();
        q1.pop();
        return f;
    } //循环移动并返回队列尾（栈顶）元素

    int top(){
        return q1.back();
    } //返队列回栈顶元素。
    
    bool empty() {
        return q1.empty();
    }//如果队列栈是空的，返回 true ；否则，返回 false 。
};

算法基本思想：

使用两个队列q1和q2来实现栈的功能。push操作直接将元素压入q1队列中。pop操作需要将q1队列中的元素移动到q2队列中，直到q1队列中只剩下一个元素，然后将该元素弹出并返回。top操作直接返回q1队列的队尾元素。empty操作判断q1队列是否为空。

时间复杂度：

push操作的时间复杂度为O(1)；

pop操作的时间复杂度为O(n)，其中n为栈中元素的个数；

top操作的时间复杂度为O(1)；

empty操作的时间复杂度为O(1)。

空间复杂度：

使用了两个队列，因此空间复杂度为O(n)，其中n为栈中元素的个数。