# Stack Using Two Queues In C++

Filed Under: C++

Today, we’ll learn to implement a stack using two queues in C++. It is a popular implementation problem and has been asked about during many technical interviews. Not just interviews, but if you are polishing your DSA concepts, then also this problem is a must. We’ll first go through the basic features of stacks and queues and then move towards the implementation.

## Difference Between Stacks And Queues

There can be many differences between a stack and a queue but let’s look at the most important difference between these data structures.

Stack: LIFO(Last In First Out): It implies that the last element to enter the stack is the first to leave.

Queue: FIFO(First In First Out): It implies that the first element to enter the queue is the first to leave.

## Problem Statement of Stack Using Two Queues

Implement a stack using two queues. Implement basic stack operations like push(), pop(), top(), etc.

Usually, we implement stack classes using vectors. Let’s move towards the concept and develop a solution to this problem.

## Concept of Stack Using Two Queues

The approach is easy to implement but has its limitations. We’ll use two queues to implement our stack class. At a time, only one of the two queues will store the data and the other will remain empty. Everything comes at a cost, to implement a stack using two queues, we’ll need to invest in more storage to provide the same functionality. Below are the steps that we’ll follow to code our custom stack class.

• The pop() function is similar in both data structures. Pushing will be different.
• To implement the push() function. We’ll proceed as follows.
• Push the new element into the empty queue.
• The new element configuration will become,
• filled_queue: [1st, 2nd, 3rd, …….. , (N – 1)th element]
• empty_queue: [Nth element]
• Push the elements from the filled_queue to empty_queue.
• Note that push() has become an expensive operation with the time complexity O(N).
• Implementation of the top() is similar to the pop() function. Just check for the currently active queue, and based on this, extract out the front() element from that queue.

## Stack Using Two Queues In C++ Program

```#include <iostream>
#include <queue>

using namespace std;

template <typename T>
class Stack
{
// public functions and data memebers of the class
public:
Stack()
{
size = 0;
flag = true;
}

// implementing the push function
void push(T element)
{
// as soon as you push an element
// increase the size of the stack
size ++;

// check which queue is currently
// storing the data
if(flag)
{
// push the element into the
// queue that is currently
// empty
q1.push(element);

// now move all the elements
// from the other queue, into
// this queue
while(!q2.empty())
{
q1.push(q2.front());
q2.pop();
}

// toggle the flag for future
// operations
flag = false;
}
else
{
q2.push(element);

while(!q1.empty())
{
q2.push(q1.front());
q1.pop();
}
flag = true;
}
}

// checking if the stack is empty
bool is_empty()
{
return size == 0;
}

void pop()
{
// before popping check if the
// stack is already empty or not
if(!is_empty())
{
size --;
if(flag)
q2.pop();
else
q1.pop();
}
else
{
cout << "The stack is already Empty" << endl;
}
}

T top()
{
if(flag)
return q2.front();
return q1.front();
}

int get_size()
{
return size;
}

// private data members of the stack
private:
// queues to hold the data
queue <T> q1;
queue <T> q2;

// size variable will store the size of the stack
int size;

// false denotes that q1 is active
// true denotes that q2 is active
// based on this member, will conduct the insertion
// and deletion operations
bool flag;
};

template <typename T>
void print_stack(Stack <T> s)
{
cout << "||*******************************************||" << endl;
cout << "The stack is :" << endl;
while(!s.is_empty())
{
cout << s.top() << endl;
s.pop();
}
cout << "||*******************************************||" << endl;
}

int main()
{
Stack <string> s;

cout << "Enter the number of elements" << endl;
int n;
cin >> n;

while(n--)
{
string str;
cin >> str;

s.push(str);
}

print_stack(s);

return 0;
}
```

## Conclusion

In this article, we learned to implement a stack class using two queues. We used the STL(Standard Template Library) queue data structure directly as our queue. We also implemented a C++ program to demonstrate the working of this stacked class. That’s all for today, thanks for reading.