Question

You must alter the Queue class you created in L5 to make it a CIRCULAR Queue class . Call your class Queue. it must be a template class.

public class Queue {

}

I have put a driver program in the module . It is called CircularQueue.java

This driver program should then run with your Queue class (no modifications allowed to the driver program).

Your Queue class should have at least the following methods: one or more constructors, enqueue, dequeue, peek, isEmpty, getSize, makeEmpty, and printQ.

printQ takes one parameter (an integer) and has return type void. printQ(30) will print 30 elements in the queue. If the queue has fewer than 30 elements (and because it is circular) then you will just keep on going round and round until you have printed out all 30.

MUST INCLUDE:

Constructor, enqueue, dequeue, peek, isEmpty, getSize, makeEmpty, printQ

// Queue.java

public class Queue {

   private Node front; // reference to first node
   private Node last; // reference to last node
   private int size; // number of nodes in queue
  
   // constructor to create an empty queue
   public Queue()
   {
       front = null;
       last = null;
       size = 0;
   }
  
   // method to insert item at the end of queue
   public void enqueue(T item)
   {
       // create a new node to store item
       Node node = new Node(item);
       if(isEmpty()) // empty queue
       {
           // set front and last node to node
           front = node;
           last = node;
       }
       else // insert at end
       {
           // set prev of node to last
           node.setPrev(last);
           // set next of last to node
           last.setNext(node);
           last = node; // update last to node
       }
      
       size++; // increment size of queue
       }
  
   // method to remove and return the front element of queue
   public T dequeue()
   {
       if(isEmpty()) // empty queue, return dummy value
           return (T) "Empty List";
       else
       {
           Node node = front; // get the node at front
           T data = (T)node.getItem();
           front = front.getNext(); // set front to node next to front
           if(front == null) // queue has become empty, set last to null
               last = null;
           else
               front.setPrev(null); // if non-empty set prev of front to null
           size--; // decrement size
           node.setNext(null); // set next of node to null
           return data; // return the front element
       }
   }
  
   // method to return the front element
   public T peek()
   {
       if(isEmpty()) // empty queue
           return (T) "Empty list";
       else // non-empty queue
           return (T)front.getItem();
   }
  
   // method to return the number of elements in the queue
   public int getSize()
   {
       return size;
   }
  
   // method to delete all the elements of the queue
   public void makeEmpty()
   {
       // set front and last to null
       front = null;
       last = null;
       size = 0; // set size to 0
   }
  
   // method to return true if queue is empty else return false
   public boolean isEmpty()
   {
       return size == 0;
   }
}
//end of Queue.java

// Q1.java

public class Q1 {
  
   public static void main(String[] args) {
      
       Queue myQ = new Queue(); //string Q

       String[] names = {"harry", "mary", "mosi", "sadie","tom", "janice"};

       for (int i=0; i

       myQ.enqueue(names[i]);

       System.out.println("Size is " + myQ.getSize());

       for (int i=0; i<6; i++)

       System.out.println(myQ.dequeue()); //test that it also works for integers

       Integer[]numbers={4,5,6,7,8,17,100};

       Queue myI = new Queue(); //Integer Q

       for (int i=0; i

       myI.enqueue(numbers[i]);

       System.out.println("Size is " + myI.getSize());

       //Verify it adds (and is an integer Q) and doesn't concatenate(String Q)

       int total=0;

       int tempSize=myI.getSize();

       System.out.println("Integers in Queue are:");

       for (int i=0; i

       //cannot use getSize() here because it changes every time you dequeue
       {
           Integer val = myI.dequeue();
           System.out.print(val+ " ");
           total=total+val;
       }

       System.out.println("\nTotal is:" + total);
   }

}

// end of Q1.java

Node.java

public class Node<T> {
//Node makes item, next, and prev all private
//and therefore has to provide accessors
//and mutators (gets and sets)
private T item;
private Node next;
private Node prev;

Node(T newItem) {
item = newItem;
next = null;
prev = null;
}

Node(T newItem, Node nextNode, Node prevNode) {
item = newItem;
next = nextNode;
prev = prevNode;
}

/**
* @return the item
*/
public T getItem() {
return item;
}

/**
* @param item the item to set
*/
public void setItem(T item) {
this.item = item;
}

/**
* @return the next
*/
public Node getNext() {
return next;
}

/**
* @param next the next to set
*/
public void setNext(Node next) {
this.next = next;
}

/**
* @return the prev
*/
public Node getPrev() {
return prev;
}

/**
* @param prev the prev to set
*/
public void setPrev(Node prev) {
this.prev = prev;
}

}

Answer 1

Answer:

You must alter the Queue class you created in L5 to make it a CIRCULAR Queue class . Call your class Queue. it must be a template class.

// Queue.java

class Node<T> {
    //Node makes item, next, and prev all private
    //and therefore has to provide accessors
    //and mutators (gets and sets)
    private T item;
    private Node next;
    private Node prev;

    Node(T newItem) {
        item = newItem;
        next = null;
        prev = null;
    }

    Node(T newItem, Node nextNode, Node prevNode) {
        item = newItem;
        next = nextNode;
        prev = prevNode;
    }

    /**
     * @return the item
     */
    public T getItem() {
        return item;
    }

    /**
     * @param item the item to set
     */
    public void setItem(T item) {
        this.item = item;
    }

    /**
     * @return the next
     */
    public Node getNext() {
        return next;
    }

    /**
     * @param next the next to set
     */
    public void setNext(Node next) {
        this.next = next;
    }

    /**
     * @return the prev
     */
    public Node getPrev() {
        return prev;
    }

    /**
     * @param prev the prev to set
     */
    public void setPrev(Node prev) {
        this.prev = prev;
    }

}

public class Queue<T> {

    // Nodes pointing to front and back of queue
    private Node<T> head;
    // current size
    private int size;

    /**
     * default constructor
     */

    public Queue() {
        head = null;
        size = 0;
    }

    /**

     * method to add an item to the back of the queue

     *

     * @param data

     * item to be added

     */

    public void enqueue(T data) {
        // creating a new node
        Node<T> node = new Node<T>(data);
        // if queue is empty, adding as the first node
        if (isEmpty()) {
            head = node;
            node.setNext(node);
            node.setPrev(node);
        } else {
            //appending at the rear end
            node.setPrev(this.head.getPrev());
            node.setNext(this.head);
            head.setPrev(node);
            node.getPrev().setNext(node);
            //updating the rear node
        }
        size++; //incrementing size
    }

    /**
     * method to remove and return the element at front position
     * @return the item removed
     */

    public T dequeue() {
        //if not empty
        if (!isEmpty()) {

            if (head.getNext() == head) {
                T res = head.getItem();
                head=null;
                size--;
                return res;
            }

            //fetching item at front
            T data = head.getItem();
            //adjusting front
            head.getPrev().setNext(head.getNext());
            head.getNext().setPrev(head.getPrev());
            head = head.getNext();
            //decrementing size
            size--;
            //returning removed data
            return data;
        }
        //queue is empty
        return null;
    }

    /**

     * method to return the element at front position without removing

     */

    public T peek() {
        if (!isEmpty()) {
            //returning item at front
            return head.getItem();
        }
        return null; //empty
    }

    /**
     * @return true if the queue is empty
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return the current size of queue
     */
    public int getSize() {
        return size;
    }

    /**
     * method to make queue empty
     */
    public void makeEmpty() {
        head = null;
        size = 0;
    }

    /**
     * return item of head of current circular queue
     * @return
     */
    public T getHead() {
        if (isEmpty()) {
            return null;
        }
        return head.getItem();
    }

    /**
     * print complete circular queue
     * @param i
     */
    public void printQ (T i){
        boolean flag = true;
        Node<T> curr = head;
        while (flag || curr != head) {
            System.out.print(curr.getItem() + " ");
            curr = curr.getNext();
            flag = false;
        }
        System.out.println();
    }
}

// CircularQueue.java:

public class CircularQueue {

    public static void main(String[] args) {
        System.out.println("String queue");
        Queue <String> myQ = new Queue<String>(); //string Q
        String[] names = {"harry", "mary", "mosi", "sadie","tom", "janice"};
        for (int i=0; i<names.length;i++)
            myQ.enqueue(names[i]);
        System.out.println("Size is " + myQ.getSize());

        System.out.println("Head is " + myQ.peek());
        System.out.println("Items in queue are: " );
        for (int i=0; i<names.length; i++)
            System.out.println(myQ.dequeue());

        //test that it also works for integers
        System.out.println("Integer queue");
        Integer[]numbers={4,5,6,7,8,17,100};
        Queue<Integer> myI = new Queue<Integer>(); //Integer Q
        for (int i=0; i<numbers.length;i++)
            myI.enqueue(numbers[i]);
        System.out.println("Size is " + myI.getSize());
        //Verify it adds (and is an integer Q) and doesn't concatenate(String Q)
        int total=0;
        int tempSize=myI.getSize();
        System.out.println("Integers in Queue are:");
        for (int i=0; i<tempSize; i++)
        //cannot use size() here because it changes every time you dequeue
        {Integer val = myI.dequeue();

            System.out.print(val+ " ");
            total=total+val;
        }
        System.out.println("\nTotal is:" + total);
        //check you have made a circular queue
        //myI was empty. So fill it up again
        for (int i=0; i<numbers.length;i++)
            myI.enqueue(numbers[i]);
        //and print 20 items, going around and around
        System.out.println("Printing 20 values");
        System.out.println("Head is " + myI.peek());
        myI.printQ(20);
        //verify makeEmpty works
        myI.makeEmpty();
        //try to peek
        System.out.println(myI.peek());
        //try to dequeue
        System.out.println(myI.dequeue());
        //what is its size?
        System.out.println("Size is " + myI.getSize());
        //add one item
        myI.enqueue(100);
        System.out.println("Size is " + myI.getSize());
        System.out.println(myI.dequeue());//dequeue only item in queue

        System.out.println("Size is " + myI.getSize()); //verify size is now 0
        System.out.println(myI.getHead());//verify no node left
    }

}

Output: