Question

C++ language

We are given a Queue data structure that supports standard operations like Enqueue() and Dequeue(): Enqueue(element): add a new element at the tail of the queue; Dequeue(): delete the element at the head of the queue.

Show how to implement a stack using two queues. Analyze the running time of the stack operations: Push and Pop.

Answer 1

Code for queue implementation:

#include <iostream>
using namespace std;
int queue[100], n = 100, front = - 1, rear = - 1;   //initially both pointer is poinred to -1 in queue
void Insert() {
   int val;
   if (front == n - 1)          //check an queue is full then we can not insert element
                cout<<"Queue Overflow"<<endl;
   else {
      if (rear == - 1)                  //check the element to be inserted is first 
                rear = 0;         // then fornt is pointed 0
      cout<<"Insert the element in queue : "<<endl;
      cin>>val;
      front++;                   //for inserting element increment front
      queue[front] = val;        //and inserted element where front is present 
   }
}
void Delete() {
   if (rear == - 1 || rear > front) {                //check an queue is empty and rear is greater than front
      cout<<"Queue Underflow ";              // then we cant delete any element from queue because its empty
      return ;
   } else {
      cout<<"Element deleted from queue is : "<< queue[rear] <<endl;   //return deleted element
      rear++;    //then increment rear
   }
}
void Display() {
   if (rear == - 1)
                cout<<"Queue is empty"<<endl;   //if rear is pointed -a then queue is empty
   else {
      cout<<"Queue elements are : ";
      for (int i = rear; i <= front; i++)            //traverse all element from that are in queue from front till front 
        cout<<queue[i]<<" ";                   //print element
      cout<<endl;  
   }
}
int main() {
   int ch;
   cout<<"1) Insert element to queue"<<endl;
   cout<<"2) Delete element from queue"<<endl;
   cout<<"3) Display all the elements of queue"<<endl;
   cout<<"4) Exit"<<endl;
   do {
      cout<<"Enter your choice : "<<endl;     //let user to choice what user want to do
      cin>>ch;
      switch (ch) {
         case 1: Insert();
         break;
         case 2: Delete();
         break;
         case 3: Display();
         break;
         case 4: cout<<"Exit"<<endl;
         break;
         default: cout<<"Invalid choice"<<endl;
      }
   } while(ch!=4);
   return 0;
}

OUTPUT

Implementation of stack using 2 queue:

For all stack operations (push, pop, isEmpty, size) time complexity is  O(1).

Stack follow the technic LIFO(Last-in-First-Out) any element insert or deleted from the top of stack. So For pish operation it directly insert element at top of stack. For pop any element we can choose element in one time so the time complexity of the stack is O(1)