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

Question

https://www.hackerrank.com/challenges/queue-using-two-stacks/problem 上面的问题需要用两个栈来实现一个队列。所以我应该做的是回答 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% 的测试用例，并给出了“超过时间限制”的结论。对效率低下的任何帮助在代码或方法中？另外我想问一下，使用类会减慢代码速度吗？

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 转移到 out：

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 弹出out.

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

Implementing Queue Using Two Stacks Time Limit Exceeded

c++

queue

stack

class