Dark Mode On/Off

A Stack is a **Last In First Out(LIFO)** structure, i.e, the element that is added last in the stack is taken out first. Our goal is to implement a Stack using Queue for which will be using two queues and design them in such a way that **pop** operation is same as dequeue but the **push** operation will be a little complex and more expensive too.

Assuming we already have a class implemented for Queue, we first design the class for Stack. It will have the methods `push()`

and `pop()`

and two queues.

```
class Stack
{
public:
// two queue
Queue Q1, Q2;
// push method to add data element
void push(int);
// pop method to remove data element
void pop();
};
```

Since we are using Queue which is **First In First Out(FIFO)** structure , i.e, the element which is added first is taken out first, so we will implement the **push** operation in such a way that whenever there is a **pop** operation, the stack always pops out the last element added.

In order to do so, we will require two queues, `Q1`

and `Q2`

. Whenever the **push** operation is invoked, we will enqueue(move in this case) all the elements of `Q1`

to `Q2`

and then enqueue the new element to `Q1`

. After this we will enqueue(move in this case) all the elements from `Q2`

back to `Q1`

.

So let's implement this in our code,

```
void Stack :: push(int x)
{
// move all elements in Q1 to Q2
while(!Q1.isEmpty())
{
int temp = Q1.deque();
Q2.enque(temp);
}
// add the element which is pushed into Stack
Q1.enque(x);
// move back all elements back to Q1 from Q2
while(!Q2.isEmpty())
{
int temp = Q2.deque();
Q1.enque(temp);
}
}
```

It must be clear to you now, why we are using two queues. Actually the queue `Q2`

is just for the purpose of keeping the data temporarily while operations are executed.

In this way we can ensure that whenever the **pop** operation is invoked, the stack always pops out the last element added in `Q1`

queue.

Like we have discussed above, we just need to use the dequeue operation on our queue `Q1`

. This will give us the last element added in Stack.

```
int Stack :: pop()
{
return Q1.deque();
}
```

When we implement Stack using a Queue the **push** operation becomes expensive.

- Push operation: O(n)
- Pop operation: O(1)

When we say "implementing Stack using Queue", we mean how we can make a Queue behave like a Stack, after all they are all logical entities. So for any data structure to act as a Stack, it should have `push()`

method to add data on top and `pop()`

method to remove data from top. Which is exactly what we did and hence accomplished to make a Queue(in this case two Queues) behave as a Stack.