Queue Data Structure

Queue Data Structure using Stack

Queue Data Structure

• A queue is defined by its FIFO (First In First Out) property, which means that the element that is inserted first is removed first. 
• As a result, instead of using an array for storage, we can use a Stack to create a Queue.
• For performing enqueue we require only one stack as we can directly push data into the stack, but to perform dequeue we will require two Stacks because we need to follow the 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 the push() method and data can be deleted using the 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;
}