For this programming assignment, you will implement a Queue whose size can grow

Question

For this programming assignment, you will implement a Queue whose size can grow as elements are inserted into the queue. You will build three different implementations of this Queue. Two of these implementations will be array-based. Each of these two should take an initial capacity for the queue in the constructor. The only difference between these implementations will be what happens when the Queue is full. For the first implementation, ArrayQueue, you should increase the size of the array by a constant amount. For the second implementation, DoublingArrayQueue, you should double the size of the array. Finally, for the third implementation, you should implement a Queue using a Linked List.

You will now time your three implementations. For each version of your queue, enqueue a large amount of random numbers onto the queue (e.g. 10 million). Time how long this takes using the StopWatch class we provided (eCampus). However, you should measure the total time at fixed intervals (e.g. every 10000 enqueue operations). For the array-based implementations, you should start with some small capacity significantly smaller than the maximum number of enqueue operations. For the ArrayQueue, your increment amount should also be significantly smaller than the number of enqueue operations. You will then graph the times for the three implementations. This process will allow you to see how your choice of implementation can affect performance.

Explanation / Answer

1st Implementation

class ArrayQueue {
   int a[];
   int size;
   final int c = 10;
   ArrayQueue(int n) {
       a = new int[n];
       size = 0;
   }
   boolean isEmpty() {
       return size==0;
   }
   boolean isFull() {
       return size==a.length;
   }
   void increaseSize() {
       int b[] = new int[a.length+c];
       int i;
       for(i=0;i<a.length;i++) {
           b[i] = a[i];
       }
       a = b;
   }
   void enqueue(int a) {
       if(isFull()) increaseSize();
       a[size++] = a;
   }
   int dequeue()throws Exception {
       if(isEmpty()) throw new Exception("Queue is empty");
       int x = a[0];
       int i;
       for(i=1;i<size;i++) a[i-1] = a[i];
       return x;
   }
}

2nd Implementation

class ArrayQueue2 {
   int a[];
   int size;
   ArrayQueue(int n) {
       a = new int[n];
       size = 0;
   }
   boolean isEmpty() {
       return size==0;
   }
   boolean isFull() {
       return size==a.length;
   }
   void increaseSize() {
       int b[] = new int[a.length*2];
       int i;
       for(i=0;i<a.length;i++) {
           b[i] = a[i];
       }
       a = b;
   }
   void enqueue(int a) {
       if(isFull()) increaseSize();
       a[size++] = a;
   }
   int dequeue()throws Exception {
       if(isEmpty()) throw new Exception("Queue is empty");
       int x = a[0];
       int i;
       for(i=1;i<size;i++) a[i-1] = a[i];
       return x;
   }
}

3rd Implementation

class QueueLL {
   LinkedList<Integer> ll;
   ArrayQueue(int n) {
       ll = new LinkedList<>();
   }
   boolean isEmpty() {
       return ll.isEmpty();
   }
   void enqueue(int a) {
       ll.addLast(a);
   }
   int dequeue()throws Exception {
       if(isEmpty()) throw new Exception("Queue is empty");
       return ll.removeFirst();
   }
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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