当前位置：首页 > news >正文

[九度1512 剑指offer7] 用两个栈实现队列

news 来源：原创 2024/4/29 12:28:53

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。

输入：

每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。

输出：

对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。

样例输入：

3
PUSH 10
POP
POP

样例输出：

10
-1

/*
*思路1：s1、s2地位等同，需要由PUSH->POP 和POP->PUSH时来回倒一下栈，顺序就正确了。
*
* */

这样倒栈的次数多了，大大降低的了效率。在九度上，最后一个大集合不能通过。

/*思路二：不用来回倒栈
 *分别分析插入和删除两种情况
 *s1作为主，S2为辅助。
 * 
 *分析删除，如果删除，s1中为逆序，s1导入s2;如果s2本身有数,说明上次导入s2的值可以依旧删除，先删S2
 *分析插入,不论s2是否有值，直接插入s1，没有任何问题。
 *
 * 总结：删除，优先s2，没有从s1 导入。插入，直接插入s1
 *
 * */

#include<iostream>
#include<stack>
#include<string>

using namespace std;
class popException{};

template<typename T>
class Queue{
public:
    //Queue(void);
    //~Queue(void);

    void push(const T& node);
    T pop();
private:
    stack<T> s1;
    stack<T> s2;
};


template<typename T>
void Queue<T>::push(const T& e)
{
    s1.push(e);
}

template<typename T>
T Queue<T>::pop(){
    T temp;
    if(s2.empty()){
        while(!s1.empty()){
            temp=s1.top();
            s1.pop();
            s2.push(temp);
        }
    }
    if(s2.empty())
        throw popException();
    T head=s2.top();
    s2.pop();
    return head;
}

int main()
{
    Queue<int> Q;
    int val,n;
    string cmd;
    cin>>n;
    for(int i=0;i<n;i++){
       cin>>cmd;
       if(cmd=="PUSH"){
           cin>>val;
           Q.push(val);
       }
       if(cmd=="POP"){
        try{
            cout<<Q.pop()<<endl;
        }catch(popException){
            cout<<-1<<endl;
        }
       }
    }

    return 0;
}

有一篇博客分析的不错：http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html