ALGO: How to implement queue by using stack ?

Question

But when priority(distance) are changed of vertex.So I have to search those vertex in priority queue(MIN heap) which distance are updated.How to find position of that vertex in binary min heap because find operation are not present in binary min heap?

Answer 1

We need two stack for implementing queue using stack.For 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. Following is the steps to be followed to implement
step1. Create InStack and OutStack with their method of enqueue and dequeue.

class Queue {
  public:
  Stack S1, S2; // two stacks one in and other is outstack
  void enqueue(int x);   //defining methods
  int dequeue();
}

step2. Stacks are for data storage in place of arrays, so we will be adding data to Stack, so define push() method,

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

step3:pop element from S1 and push to S2 util S1 gets empty then we pop from S2 which will use FIFO approach.

int Queue :: dequeue() {
  while(S1.isEmpty()) {
    x = S1.pop();
    S2.push();
  }
  x = S2.pop();    //removing the element,it will be the first element to be removed.
  while(!S2.isEmpty()) {     // after pop operation copy S2 items to S1
    x = S2.pop();
    S1.push(x);
  }
  return x;
}