# Queue Using Two Stacks Problem In C++

Filed Under: C++ Today, we’ll learn to solve the queue using two problem stacks in C++. It is a classical implementation problem and has been asked about during many technical interviews. This problem is a must if you’re brushing up on your DSA concepts. Let’s quickly take a look at the basic differences between stacks and queues. Later we’ll move towards the implementation.

Also read: Stack Using Two Queues In C++

## 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.

### Stacks

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

#### Unique Stack Functions

• pop(): Pops the element at the top of the stack.
• top(): Returns the topmost element of the stack.

### Queues

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

#### Unique Queue Functions

• pop(): Pops the element at the front of the queue.
• front(): Returns the element at the front of the queue.

## Problem Statement of Queue Using Two Stacks

Implement a queue using two stacks. Implement basic queue operations like push(), pop(), front(), etc.

Usually, we implement queue classes using vectors. But let’s implement a custom queue class using stacks.

## Approach to Solve Queue Using Two Stacks

To implement this queue class we’ll proceed in the following manner.

• We’ll push() the data into the stacks in such a manner that whenever we call the pop() function, it’ll delete the element as if it was a queue.
• To implement the push() function. We’ll take the following steps.
• After the N – 1 push() operation, the stacks will look like this,
• s1: [(N – 1)th item, …….., 3rd, 2nd, 1st] –> TOP
• s2: [] –> TOP
• Now, transfer all the elements of s1 into s2. And push the Nth element into s2.
• After this, transfer all the elements back into s1.
• Now, the configuration of the stack becomes,
• s1: [Nth item, (N – 1)th item, …….., 3rd, 2nd, 1st] –> TOP
• s2: [] –> TOP
• Note that push() has become an expensive operation with the time complexity O(N).
• Notice that, if we call pop() on the stack, it’ll remove the first item. This means that our data structure is functioning like a queue.
• To implement the front(), we’ll simply call the top() function on the active stack. And this would do the work for us.

## Queue Using Two Stacks Problem In C++ Program

```#include <iostream>
#include <stack>

using namespace std;

template <typename T>
class Queue
{
// private data members of the queue
private:
// queues to hold the data
stack <T> s1;
stack <T> s2;

// variable to store the size of the queue
int size;

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

// public functions and data memebers of the class
public:
// initialize the size of the queue with 0
Queue(): size(0) {}

// implementing the push function
void push(T element)
{
// increase the size of the queue
size++;

// first put all the elements of s1
// into s2
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}

// now insert the new element into s2
s2.push(element);

// now transfer all the elements of s2
// into s1
while(!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
}

// 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 --;
s1.pop();
}
else
{
cout << "The queue is already Empty" << endl;
}
}

T front()
{
return s1.top();
}

int get_size()
{
return size;
}
};

template <typename T>
void print_queue(Queue <T> q)
{
cout << "||*******************************************||" << endl;
cout << "The queue is :" << endl;
while(!q.is_empty())
{
cout << q.front() << endl;
q.pop();
}
cout << "||*******************************************||" << endl;
}

int main()
{
Queue <string> q;

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

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

q.push(str);
}

print_queue(q);

return 0;
}
```

## Conclusion

In this article, we learned to implement a queue class using two stacks. We used the STL(Standard Template Library) to make use of the queue. We also implemented a C++ program to demonstrate the working of this custom queue class. That’s all for today, thanks for reading.