CODEWITHSUNDEEP
c++stlqueuestackswap
Ikshul Dureja
Ikshul Dureja

Reputation: 77

Error in using swap() STL while implementing Queue using two Stacks

I was trying to implement Class Queue using Two Stacks and I noticed an error. If I swap both the stacks(after pop and front operation), using swap() operation of STL, I am getting wrong answer but when I swap both the stacks using static code, then I am getting the correct answer. Please let me know what exactly is happening.

#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Queue{
    stack<T> A;//non empty stack
    stack<T> B;
    public:
    void push(T x){//O(1)
        A.push(x);
    };
    void pop(){//O(n)
        if(A.empty()) return;
        while(A.size()>1){
            T element=A.top();
            A.pop();
            B.push(element);
        }
        //1 element remaining in A
        A.pop();
        //swap(A,B);//so that A is the non empty stack
        //using swap() in this case was giving wrong answer

        while(!B.empty()){
            T element=B.top();
            B.pop();
            A.push(element);
        }
    };
    int front(){//O(n)
        while(A.size()>1){
            T element=A.top();
            A.pop();
            B.push(element);
        }
        T element = A.top();
        A.pop();
        B.push(element);
        while(!B.empty()){
            T element = B.top();
            B.pop();
            A.push(element);
        }
        return element;
    };
    int size(){
        return A.size()+B.size();
    };
    bool empty(){
        return size()==0;
    };


};
int main() {
    Queue<int> q;
    q.push(2);
    q.push(3);
    q.push(4);
    q.pop();
    q.push(15);
    while(!q.empty())
    {
        cout<<q.front()<<" ";
        q.pop();
    }
    return 0;
}

One more thing, I implemented Stack using two Queues before this, and there swap() was giving correct answer.

Upvotes: 0

Views: 43

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32727

When you swap your stacks manually, you do it by taking one element off of the top of one stack and putting it on top of the other. This will reverse the order of elements in the stack.

When you use std::swap to swap the two stacks, the current order is preserved. The end result is that the order in the stack is reversed. By using another manual "swap", you re-reverse all the elements and the original order is restored (but with the bottom element removed, since you don't add it to the B stack during the swap).

Upvotes: 1

Related Questions