Question

Implementation of a a queue with a "circular" array or a "regular" array.

(a) "circular" array: consider using the smallest number of fields/variables in a struct/class. List the fields/variables that support the enqueue and dequeue operations in O(1) time in the worst case. Explain why the list is the smallest and the two operations are O(1) time.

(b) "regular" array: explain the worst-case time complexity in big-O for the operations (queue size is at most n).

Answer 1

enque and deque of circular queue will execute in constant time(as there is no loop). so the complexity is O(1).

though, enque of linear queue is O(1) but deque require a loop, and it is O(n).

Queue.cpp

#include<iostream>
#include<stdlib.h>

using namespace std;

template <class T>
class Queue {
   protected:
   int size, front=-1, back=-1;
   T** values;
   public:
   Queue(int s) {
       size = s;
       values = (T**)malloc(s*sizeof(T*));
   }
   virtual void enqueue(T* value){};
   virtual T* dequeue() = 0;
};

template <class T>
class CircularQueue:public Queue<T> {
   public:
   CircularQueue(int s):Queue<T>(s){}
   virtual void enqueue(T* value) {
       if(Queue<T>::front==-1 && Queue<T>::back==-1) {
           Queue<T>::front=Queue<T>::back=0;
           Queue<T>::values[Queue<T>::back]=value;
       } else {
          
           if((Queue<T>::back+1)%Queue<T>::size==Queue<T>::front) {
               // Queue is full
           } else {
               Queue<T>::back++;
               Queue<T>::back%=Queue<T>::size;
               Queue<T>::values[Queue<T>::back]=value;
           }
       }
   }
          
   virtual T* dequeue() {
       if(Queue<T>::front==-1 && Queue<T>::back==-1) {
           // underflow
           return 0;
       }
       T* t = Queue<T>::values[Queue<T>::front];
      
       if(Queue<T>::back==Queue<T>::front) {
           Queue<T>::back = Queue<T>::front = -1;
       } else {
           Queue<T>::front++;
           Queue<T>::front%=Queue<T>::size;
       }
       return t;
   }
};

template <class T>
class LinearQueue:public Queue<T> {
   public:
   LinearQueue(int s):Queue<T>(s){}
   virtual void enqueue(T* value) {
       if(Queue<T>::front==-1 && Queue<T>::back==-1) {
           Queue<T>::front=Queue<T>::back=0;
           Queue<T>::values[Queue<T>::back]=value;
       } else {
          
           if(Queue<T>::back==Queue<T>::size) {
               // Queue is full
           } else {
               Queue<T>::back++;
               Queue<T>::values[Queue<T>::back]=value;
           }
       }
   }
          
   virtual T* dequeue() {
       if(Queue<T>::front==-1 && Queue<T>::back==-1) {
           // underflow
           return 0;
       }
       T* t = Queue<T>::values[Queue<T>::front];
      
       if(Queue<T>::back==Queue<T>::front) {
           Queue<T>::back = Queue<T>::front = -1;
       } else {
          
           Queue<T>::front++;
           for(int i=Queue<T>::front;i<=Queue<T>::back;i++) {
               Queue<T>::values[i-Queue<T>::front]=Queue<T>::values[i];
           }
           Queue<T>::back = Queue<T>::back-Queue<T>::front;
           Queue<T>::front = 0;
       }
       return t;
   }
};

int* i(int value) {
   int *v = (int*)malloc(sizeof(int));
   *v=value;
   return v;
}

int main() {
   Queue<int> *q = new CircularQueue<int>(5);
   cout<<"Circular Queue of size 5"<<endl;
   cout<<"enquing 5..."<<endl;
   q->enqueue(i(5));
   cout<<"enquing 7..."<<endl;
   q->enqueue(i(7));
   cout<<"enquing 4..."<<endl;
   q->enqueue(i(4));
   cout<<"enquing 3..."<<endl;
   q->enqueue(i(3));
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<"enquing 2..."<<endl;
   q->enqueue(i(2));
   cout<<"enquing 9..."<<endl;
   q->enqueue(i(9));
   cout<<"enquing 1..."<<endl;
   q->enqueue(i(1));
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
  
   q = new LinearQueue<int>(5);
   cout<<"Linear Queue of size 5"<<endl;
   cout<<"enquing 5..."<<endl;
   q->enqueue(i(5));
   cout<<"enquing 7..."<<endl;
   q->enqueue(i(7));
   cout<<"enquing 4..."<<endl;
   q->enqueue(i(4));
   cout<<"enquing 3..."<<endl;
   q->enqueue(i(3));
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<"enquing 2..."<<endl;
   q->enqueue(i(2));
   cout<<"enquing 9..."<<endl;
   q->enqueue(i(9));
   cout<<"enquing 1..."<<endl;
   q->enqueue(i(1));
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   cout<<*(q->dequeue())<<" dequed"<<endl;
   return 0;
}

output

Circular Queue of size 5
enquing 5...
enquing 7...
enquing 4...
enquing 3...
5 dequed
7 dequed
4 dequed
enquing 2...
enquing 9...
enquing 1...
3 dequed
2 dequed
9 dequed
1 dequed
Linear Queue of size 5
enquing 5...
enquing 7...
enquing 4...
enquing 3...
5 dequed
7 dequed
4 dequed
enquing 2...
enquing 9...
enquing 1...
3 dequed
2 dequed
9 dequed
1 dequed