1. How do the markers queueHead and queueTail relate with each other in case of

Question

1. How do the markers queueHead and queueTail relate with each other in case of an empty queue implemented using circular array 2. How do the markers queueHead and queueTail relate with each other in a queue having only one element where the queue is implemented using circular array. 3. How do we update the queueHead marker in case of circular array based queue implementation? 4. How do we update the queueTail marker in case of circular array based queue implementation? 5. How do we initialize the queueHead and queueTail in case of circular array for queue 6. Define the parameterized constructor of queueADT as described in Figure 1. 7. Define the getFront function in queueADT class design as described in Figure - 1 8. Define the getEnd function in queueADT class design as described in Figure 1 9. Complete the definition of insertQueue function as described in the Figure -1 10.Complete the definition of removeQueue function as described in the Figure 1

Explanation / Answer

1.) At the begining the queueHead is marked at 0 and queueTail is marked at the last position of the queue i.e.(maxQueueSize -1) . So in the empty queue queueHead = 0 and queueTail = maxQueueSize -1

2) If there is one element in the circular queue. When there is no element in the queue then queueHead = 0 and queueTail = maxQueueSize -1 . So when we insert first element we insert at location (1+queueTail)%maxQueueSize and update the queueTail = (1+queueTail)%maxQueueSize . As queue tail before inserting first elelemt was queueTail = maxQueueSize -1 . So we we insert the first element at (1+maxQueueSize-1)%maxQueueSize and that will be 0.

So after inserting first element queueHead = 0 and queueTail = 0;

3) queueHead remains fixed while inserting the element we only move the queueTail while inserting the element. But while removing the element queueHead moves one step further. in removal process we update the queueHead to (queueHead + 1)%(maxQueueSize).

4.) In cirucular queue queueTail remains fixed while removing the element it only moves while inserting the element in the circularQueue. when we insert the element in the circularQueue the queueTail updates to (queueTail + 1) %(maxQueueSize) i.e. queueTail = (queueTail + 1) %(maxQueueSize)

5.) In circularQueue implementation . queueHead is initialized to 0 while queueTail is initialized to maxQueueSize -1

6.) parametrized constructor for the queueADT (As your haven't provided the initialSize of the queueArray i am considering it as 10). Below is the code

queueADT(int size = 10){
   queueArr = new int[size];
   maxQueueSize = size;
   queueLen = 0;
   queueHead = 0;
   queueTail = size -1;
  }

7.) getFront :

int getFront(){
   if(queueLen == 0){
    cout<<"Queue Empty"<<endl;
    return -999;
   }else{
    return queueArr[queueHead];
   }
  }

8.) getEnd Function :

int getEnd(){
   if(queueLen == 0){
    cout<<"Queue Empty"<<endl;
    return -999;
   }else{
    return queueArr[queueTail];
   }
  }

9.) insertQueue(int element):

void insertQueue(int element){
   if(!isFull()){
   
    queueArr[(queueTail +1)%(maxQueueSize)] = element;
    queueTail = (queueTail +1)%(maxQueueSize);
    queueLen++;
   }else{
    cout<<"Queue Full"<<endl;
   }
  }

10.) removeQueue():

void removeQueue(){
   if(!isEmpty()){
    queueHead = (queueHead + 1) % (maxQueueSize);
    queueLen--;
   }else{
    cout<<"Queue Empty"<<endl;
   }
  }

/************************************ For your simplicity below is the Complete Code ***************/

#include<iostream>
using namespace std;

class queueADT{
int maxQueueSize;
int queueLen;
int queueHead;
int queueTail;
int *queueArr;

public:
  queueADT(int size = 10){
   queueArr = new int[size];
   maxQueueSize = size;
   queueLen = 0;
   queueHead = 0;
   queueTail = size -1;
  }
  
  void intqueue(){
   queueLen = 0;
   queueHead = 0;
   queueTail = maxQueueSize -1;
  }
  bool isEmpty(){
   return queueLen ==0;
  }
  
  bool isFull(){
   return queueLen == maxQueueSize;
  }
  int getFront(){
   if(queueLen == 0){
    cout<<"Queue Empty"<<endl;
    return -999;
   }else{
    return queueArr[queueHead];
   }
  }
  
  int getEnd(){
   if(queueLen == 0){
    cout<<"Queue Empty"<<endl;
    return -999;
   }else{
    return queueArr[queueTail];
   }
  }
  
  void insertQueue(int element){
   if(!isFull()){
   
    queueArr[(queueTail +1)%(maxQueueSize)] = element;
    queueTail = (queueTail +1)%(maxQueueSize);
    queueLen++;
   }else{
    cout<<"Queue Full"<<endl;
   }
  }
  
  void removeQueue(){
   if(!isEmpty()){
    queueHead = (queueHead + 1) % (maxQueueSize);
    queueLen--;
   }else{
    cout<<"Queue Empty"<<endl;
   }
  }
  
  void display(){
   int i;
        if( queueHead <= queueTail){
    for(i=queueHead; i<=queueTail;i++)
     cout << queueArr[i]<<" ";
        }
        else{
   for(i=queueHead;i<maxQueueSize;i++){
        cout <<queueArr[i] << " ";
    }
   
   for(i=0;i<=queueTail;i++){
        cout << queueArr[i]<< " ";
    }
        }

  }
};

int main(){
queueADT q1;
q1.insertQueue(12);
q1.insertQueue(13);
q1.insertQueue(15);
q1.insertQueue(23);
q1.insertQueue(24);
q1.insertQueue(25);
q1.insertQueue(26);
q1.insertQueue(27);
q1.insertQueue(28);
q1.insertQueue(29);
//q1.insertQueue(30);
//q1.insertQueue(31);
cout<<"After insertion circular Array is "<<endl;
q1.display();
cout<<endl;
cout<<"Removing Element"<<endl;
q1.removeQueue();
cout<<"After removal Circular Array is "<<endl;
q1.display();
cout<<endl;
cout<<"Removing Element"<<endl;
q1.removeQueue();
cout<<"After removal Circular Array is "<<endl;
q1.display();
cout<<endl;
cout<<"Inserting element"<<endl;
q1.insertQueue(26);
cout<<"After insertion Circular Array is"<<endl;
q1.display();
cout<<endl;
cout<<"Removing Element"<<endl;
q1.removeQueue();
cout<<"After removal Circular Array is "<<endl;
q1.display();
cout<<endl;
}

  

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.