Thu. Oct 6th, 2022

All android in one place

# Stack Implementation in C++ Using Two Queues In this article, we will learn stack implementation using two queues. Stacks are very crucial data structures and are used everywhere in our day-to-day life. We will start by understanding the concept of stacks and queues and then move towards the implementation in the end.

Also read: Stack Class Implementation In C++ [Easy]

## What Is A Stack?

Okay let’s come straight to the point, what does a stack represent? As the name suggests, a stack is simply a stack. A stack follows the LIFO(Last In First Out) property i.e. the object that enters the stack, in the end, is the first to come out.

## What Is A Queue?

A queue represents a FIFO(First In First Out) data structure, which means that the first element to enter the queue is the first one to exit it. You have many encounters with queues in your day-to-day life. Be it the process manager of your computer or movie ticket counter, yes I know that there are not many who buy tickets from the ticket counter. But queues have always been an indispensable part of our lives.

## Stack Using Two Queues

Let’s quickly jump to developing a stack using two queues. Below are the steps that we will follow while writing the code.

• At a time only one queue will store the data and the other will remain empty
• To implement the push function, we follow the steps given below
• Add the new element in the empty queue
• Move all the elements of the other queue into this queue
• Just remove the element at the front of the queue having the data.
• We can obtain the top most element of the stack by using the front() function on the queue having the data.

The following example will help you grab the concept better.

1. Let’s start with an empty stack

Stack : |Empty|
Queue1 : |Empty|
Queue2 : |Empty|

2. Push “Vaibhav” into the stack

```Stack : |Vaibhav| <-- Top
Queue1 : |Vaibhav| --> Head
Queue2 : |Empty|
```

3. Push “Hardik” into the stack

```Stack : |Vaibhav| <-- |Hardik| <-- Top
Queue1 : |Vaibhav| --> Head
Queue2 : |Hardik| --> Head

Now we move the elements of Queue1 to Queue2

Queue1 : |Empty|
Queue2 : |Vaibhav| --> |Hardik| --> Head
```

4. Push “Malik” into the stack

```Stack : |Vaibhav| <-- |Hardik| <-- |Malik| <-- Top
Queue1 : |Malik| --> Head
Queue2 : |Vaibhav| --> |Hardik| --> Head

Now we move the elements of Queue2 to Queue1
Queue1 : |Vaibhav| --> |Hardik| --> |Malik| --> Head
Queue2 : |Empty|
```

5. Popping an element out of the stack

```Stack : |Vaibhav| <-- |Hardik| <-- Top
Queue1 : |Vaibhav| --> |Hardik| --> Head
Queue2 : |Empty|

This is very simple, we just need to remove the front element of the Queue having the elements
```

## Stack Implementation Using Two Queues In C++

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

using namespace std;

template <typename T>
class Stack
{
private:

// all the data members are private to avoid foreign access
queue <T> q1;
queue <T> q2;
int stack_size;
bool active;

public:
// constructor
Stack(): stack_size(0), active(true) {}

// push function
void push(T element)
{
// increment the size
stack_size ++;
if(active)
{
// push logic
q1.push(element);

while(!q2.empty())
{
q1.push(q2.front());
q2.pop();
}
active = false;
}
else
{
q2.push(element);

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

bool is_empty()
{
return stack_size == 0;
}

void pop()
{
// before call the pop function
// check if the stack is empty or not
if(!is_empty())
{
stack_size --;
if(active)
q2.pop();
else
q1.pop();
}
else
cout << "Already Empty !!!" << endl;
}

T top()
{
// returning the topmost element from
// the queue currently storing the data
if(active)
return q2.front();

return q1.front();
}

int get_size()
{
return stack_size;
}
};

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;
cout << endl ;
}

int main()
{
Stack <string> s;

cout << "Enter the elements and press |done| to stop" << endl;
while(true)
{
string str;
cin >> str;

if(str == "done")
break;

s.push(str);
}

print_stack(s);

cout << "Let's remove the last two elements from the stack" << endl;
s.pop();
print_stack(s);
s.pop();
print_stack(s);

return 0;
}

```

## Conclusion

Let’s recall what we learned today, we started by looking at what are stacks and queues. Then we moved to the structure of the stack class using two queues. In the end, we wrote a C++ program to demonstrate the working of our template stack class. That’s all for now, thanks for reading.

To read more about stacks and queues, you can refer to the following websites.

#### You may have missed 6 min read

#### How a Decade of Innovation Resulted in Samsung’s Z Flip4 and Fold4 – Samsung Global Newsroom 6 min read

#### Samsung Electronics Envisions Hyper-Growth in Memory and Logic Semiconductors Through Intensified Industry Collaborations at Samsung Tech Day 2022 1 min read

#### Results Are In – State of Mobile Jobs Survey 2022! 1 min read