题目描述

• 用两个队列实现栈

解题思路

• 剑指Offer 71

代码

#include<iostream>
#include<queue>
using namespace std;

class Solution{
public:
     void push(int node) {
        if(queue1.empty() && queue2.empty()){
            queue1.push(node);
        }
        else{
            if(!queue1.empty()){
                queue1.push(node);
            }
            else{
                queue2.push(node);
            }
        }
    }

    int pop() {
        int temp;
        
        // 如果queue1不为空，则将queue1前n-1个元素压入queue2
        if(!queue1.empty()){
            int tt = queue1.size()-1;
            for(int i=0; i<tt; i++){
                queue2.push(queue1.front());
                queue1.pop();
            }
            temp = queue1.front();
            queue1.pop();
        }
        else{ // 如果queue2不为空，则将queue2前n-1个元素压入queue1
            int tt = queue2.size()-1;
            for(int i=0; i<tt; i++){
                queue1.push(queue2.front());
                queue2.pop();
            }
            temp = queue2.front();
            queue2.pop();
        }
        return temp;
    }

private:
    queue<int> queue1;
    queue<int> queue2;
};

main(){
    Solution ss;

    // ss.push(1);
    // ss.push(2);
    // ss.push(3);
    // cout<<ss.pop();
    // cout<<ss.pop();
    // ss.push(4);
    // cout<<ss.pop();
    // ss.push(5);
    // cout<<ss.pop();
    // cout<<ss.pop();

    ss.push(1);
    ss.push(2);
    ss.push(3);
    ss.push(4);
    ss.push(5);
    cout<<ss.pop();
    cout<<ss.pop();
    cout<<ss.pop();
    cout<<ss.pop();
    cout<<ss.pop();
}

• 第一组测试输出为: 32451
• 第二组测试输出为: 54321

总结展望

• 题目相当不错，值得深思...

参考

• C++ 栈和队列的介绍与使用