两个队列实现栈

思路:

由于对于队列是先进先出的结构,但是栈是后入先出的结构,所以可以用两个队列实现栈。

1.入栈操作就是将元素入队列1
2.出栈操作就是需要将队列1中的除了最后一个元素外的其他元素都移动到队列2中
3.再将队列1中的最后一个元素出栈,将队列2中的元素放回队列1中
4.获得栈顶元素就是获得队列1的队尾元素
5.判断栈是否为空就是判断队列1和队列2是否都为空

代码:

class Solution {
public:
    //将需要插入栈的元素插入队列1中即可
     void push(int x){
        q1.push(x);
     }
     //将栈顶元素出栈,需要将队列1中前面的除了最后一个元素都移动到队列2中
     //再将队列1中的这个元素出队列1,就是出栈
     //之后再将队列2中的元素移动回队列1
     int pop(){
        while(q1.size()>1){
            q2.push(q1.front());
            q1.pop();
        }
        int temp=q1.front();
        q1.pop();
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
        return temp;
     }
     //栈顶元素就是队列1中的队尾元素
     int top(){
        return q1.back();
     }
     //只有当两个队列都为空的时候栈才是空
     bool empty(){
        return (q1.empty())&&(q2.empty());
     }
private:
//定义两个STL中的队列queue,分别为q1和q2
//由于栈是后入先出的结构,如果只有一个队列只能实现元素存入栈中
//但是对于出栈操作,由于栈是后入先出,但是队列是先入先出,所以想在队列1中让最后一个元素先出去,就需要将队列1中前面的所有元素都先移动到队列2中,
//让最后一个元素从队列1中出栈,再把队列2中的元素放回队列1中
    queue<int>q1;
    queue<int>q2;
};