Queue Data Structure using Stack

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 methods
  
  void enqueue(int x);
  
  int dequeue();
}

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 element
  x = S2.pop();
  
  while(!S2.isEmpty()) {
    x = S2.pop();
    S1.push(x);
  }
  
  return x;
}

---