Implement stack using two queues

Problem: Given a queue data structure that supports standard operations like enqueue() and dequeue(), implement a Stack using given queue data structure.

Approach: Stack can be implemented using two queues. There are two ways to implement it; one by making push operation costly and one by making pop operation costly.

I am preferring the way in which pop operation is costly as push operations are always more than or equal to pop operations. Following are the steps for push and pop -

push(i)

1. Enqueue i to q1.

pop()  

1. One by one dequeue each item except the last element from q1 and enqueue to q2.
2. Dequeue the last item of q1, this will be the return value.
3. Swap the names of q1 and q2 (pointers).
4. Return the item obtained in step 2.

Implementation:

class Stack

{

public:

Stack():m_q1(new std::queue<int>()), m_q2(new std::queue<int>()){}

void push(int i);

int pop();

bool isEmpty();

~Stack(){delete m_q1; delete m_q2;}

private:

std::queue<int> *m_q1, *m_q2;

};

void Stack::push(int i)

{

m_q1->push(i);

}

int Stack::pop()

{

if(isEmpty())

return -1; //Error

while(m_q1->size() > 1)

{

int temp = m_q1->front();

m_q2->push(temp);

m_q1->pop();

}

int retVal = m_q1->front();

m_q1->pop();

std::queue<int>* tempQ = m_q1;

m_q1 = m_q2;

m_q2 = tempQ;

return retVal;

}

bool Stack::isEmpty()

{

return m_q1->empty();

}

Complexity: push - O(1), pop - O(n)