A Queue is defined by its property of FIFO, which means First in First Out, i.e the element which is added first is taken out first. Hence we can implement a Queue using Stack for storage instead of array.

For performing **enqueue** we require only one stack as we can directly **push** data into stack, but to perform **dequeue** we will require two Stacks, because we need to follow queue's FIFO property and if we directly **pop** any data element out of Stack, it will follow LIFO approach(Last in First Out).

#### Implementation of Queue using Stacks

In all we will require two Stacks, we will call them InStack and OutStack.

class Queue { public: Stack S1, S2;//defining methodsvoidenqueue(int x); intdequeue(); }

We know that, Stack is a data structure, in which data can be added using **push()** method and data can be deleted using **pop()** method. To learn about Stack, follow the link : Stack Data Structure

#### Adding Data to Queue

As our Queue has Stack for data storage in place of arrays, hence we will be adding data to Stack, which can be done using the `push()`

method, hence :

void Queue ::enqueue(int x) { S1.push(x); }

#### Removing Data from Queue

When we say remove data from Queue, it always means taking out the First element first and so on, as we have to follow the FIFO approach. But if we simply perform `S1.pop()`

in our **dequeue** method, then it will remove the Last element first. So what to do now?

int Queue :: dequeue() { while(S1.isEmpty()) { x = S1.pop(); S2.push(); }//removing the elementx = S2.pop(); while(!S2.isEmpty()) { x = S2.pop(); S1.push(x); } return x; }