Queue Data Structure using Stack


The queue data structure has the property of FIFO that is first in, first out which means that the element that is inserted first will be taken out first also. For storage we can implement the queue data structure by using stack instead of using array.

To perform the enqueue operation we will need only one stack as stack will directly push the data. To perform dequeue operation two stacks will be required because FIFO should be followed. If we directly pop any element then LIFO will be followed. To avoid this we use two stacks to perform dequeue operation.


Implementation of Queue using Stack:

To implement queue using stack we will require two stacks named InStack and OutStack. Consider the following lines of code:

CODE:

class Queue

{

public:

Stack s1, s2;

void enqueue (int d);

int dequeue ();

}


Adding data to Queue:

The data will be added to stack because the queue is using stack for storage purposes using the push () function. Consider the following lines of code to add data:

CODE:

void queue :: enqueue (int d) {

  s1.push (d);

}


Removing data from Queue:

If we directly perform pop () operation then LIFO will be followed but we have to follow the FIFO. To overcome this problem we will pop the elements from s1 and then we will push them into s2. Consider the following lines of code to do this:

CODE:

int queue :: dequeue ()

{

  while (s1. isEmpty ()) {

    d = s1. pop ();

    s2. push ();

  }

  d = s2. pop ();

  while (!s2. isEmpty ())

{

    d = s2. pop ();

    s1. push (d);

  }

  return d;

}

The isEmpty () function is used to check if the stack or queue is empty or not. If the stack is empty the loop will not be executed.