dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

Queue.java (1952B)

      1 package lab6;
      2 
      3 public class Queue<T> implements QueueInterface<T> {
      4 
      5     T [] items;
      6     int front;
      7     int back;
      8     int numItems;
      9 
     10     public Queue() {
     11         front = back = numItems = 0;
     12         items = (T[]) new Object[3];
     13     }
     14 
     15     public boolean isEmpty() {
     16         if (numItems == 0) {
     17             return true;
     18         }
     19         return false;
     20     }
     21 
     22     public void enqueue(T newItem)
     23         throws QueueException {
     24         if (numItems == items.length) {
     25             resize();
     26         }
     27             items[back] = newItem;
     28             back = (back + 1) % items.length;
     29             numItems ++;
     30     }
     31 
     32     public T dequeue()
     33         throws QueueException {
     34         if (numItems != 0) {
     35             T item = items[front];
     36             items[front] = null;
     37             front = (front + 1) % items.length;
     38             numItems--;
     39             return item;
     40         }
     41         else {
     42             throw new QueueException("QueueException: Queue is empty on dequeue");
     43         }
     44     }
     45 
     46     public void dequeueAll() {
     47         items = (T[]) new Object[3];
     48         front = back = numItems = 0;
     49     }
     50 
     51     public T peek()
     52         throws QueueException {
     53         if (numItems != 0) {
     54             return items[front];
     55         }
     56         else {
     57             throw new QueueException("QueueException: Queue is empty on peek");
     58         }
     59     }
     60 
     61     protected void resize() {
     62         T []tmp;
     63         tmp = (T[]) new Object[numItems*2 + 1];
     64         for (int i = 0; i < items.length; i++) {
     65             tmp[i] = items[(front + i) % items.length];
     66         }
     67         front = 0;
     68         back = numItems;
     69         items = tmp;
     70     }
     71 
     72     @Override
     73     public String toString() {
     74         String result = "Queue of size " + numItems + " has the following items: ";
     75         if(numItems == 0)
     76             result = "No items";
     77         for(int i = 0; i < numItems; i++) {
     78             result += items[(i + front) % items.length] + " ";
     79         }
     80         return result;
     81     }
     82 }
     83