**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)**

- Enqueue i to q1.

**pop()**

- One by one dequeue each item except the last element from q1 and enqueue to q2.
- Dequeue the last item of q1, this will be the return value.
- Swap the names of q1 and q2 (pointers).
- 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)

## No comments:

## Post a Comment