c++ - 使用两个堆栈实现队列超过时间限制

Question

https://www.hackerrank.com/challenges/queue-using-two-stacks/problem 上面的问题需要使用两个栈来实现一个队列。所以我应该做的是回答 3 种类型的查询

1. 入队
2. 出队
3. 打印顶部

我的代码如下：/*

    #include <iostream>
    #include <stack>
    using namespace std;
    
    class QueueTwoStack{
        stack<int> s1;
        stack<int> s2;
        public:
        void enqueue(int x);
        void dequeue();
        int Front();
    };
    void QueueTwoStack::enqueue(int x){ //ENQUEUE
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while(!s2.empty()){
            s1.push(s2.top());
            s2.pop();
        }
    }
    void QueueTwoStack::dequeue(){  //DEQUEUE
        if(!s1.empty())
        s1.pop();
    }
    int QueueTwoStack::Front(){ //RETURN FRONT
        return s1.top();
    }
    int main() {
        QueueTwoStack Queue;
        int q,ch,x;
        cin>>q;
        while(q--){
            cin>>ch;
            if(ch==2)
            Queue.dequeue();
            else if(ch==3)
            cout<<Queue.Front()<<endl;
            else if(ch==1){
                cin>>x;
                Queue.enqueue(x);
            }
        }
        return 0;
    }
*/

现在，此代码通过了 25% 的测试用例并给出“超出时间限制”的判断。关于代码或方法效率低下的任何帮助？另外我想问一下，使用类会减慢代码吗？

标签： c++classstackqueue

Answer 1

您正在堆栈中维护一个完全排序的队列，s1通过将所有元素推入 将元素s1排入队列s2，添加下一个元素，然后将所有元素推s2回s1。这不是很理想。

让我们改为调用堆栈in和out. 一开始两者都是空的：

in:  <top>
out: <top>

排队元素只是将它们添加到in. 添加1,2,3：

Add 1:
in:  1 <top>
out: <top>

Add 2:
in:  1 2 <top>
out: <top>

Add 3:
in:  1 2 3 <top>
out: <top>

出队元素只是将它们拉出out- 需要注意的是，如果out是空的，我们将全部转移in到outfirst：

Dequeue:
in:  1 2 3 <top>
out: <top>            <- empty! Transfer

in:  <top>
out: 3 2 1 <top>

Out no longer empty, pop 1:

in:  <top>
out: 3 2 <top>

这样做可以确保每个元素只被准确地触摸三次：第一次添加到 时in，第二次从转移in到out时，第三次从 弹出out。