Working with Queues (50 pts) Due: Submit all related files by the posted due dat

Question

Working with Queues (50 pts)

Due: Submit all related files by the posted due date. Make sure that your code contains comments explaining your code.

Use Chapter 14 as a guide to complete the following part 1 and 2 below. You can delete references to the jsjf exceptions (you may also need to modify the code as well in parts that reference it).

Part 1. Complete the implementation of the LinkedQueue class presented in this chapter. Specifically, complete the implementation of the first, isEmpty, size and toString Methods. Also create a driver class (main) to test the functionality of the methods of your program. ToString should print all the elements in the Queue.

Part 2. Complete the implementation do the CircularArrayQueue class described in chapter 14, including all methods. Also create a driver class (main) to test the functionality of the methods of your program.

Explanation / Answer

Part 1:

import java.util.NoSuchElementException;

public class LinkedQueue<Item> {
    private int N;         // number of elements on queue
    private Node first;    // beginning of queue
    private Node last;     // end of queue

    // helper linked list class
    private class Node {
        private Item item;
        private Node next;
    }

    /**
     * Initializes an empty queue.
     */
    public LinkedQueue() {
        first = null;
        last = null;
        N = 0;
    }

    /**
     * Is this queue empty?
     * @return true if this queue is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this queue.
     * @return the number of items in this queue
     */
    public int size() {
        return N;   
    }

    /**
     * Returns the item least recently added to this queue.
     * @return the item least recently added to this queue
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }

    /**
     * Adds the item to this queue.
     * @param item the item to add
     */
    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else
           oldlast.next = last;
        N++;
    }

    /**
     * Removes and returns the item on this queue that was least recently added.
     * @return the item on this queue that was least recently added
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = first.item;
        first = first.next;
        N--;
        if (isEmpty()) last = null;   // to avoid loitering
        return item;
    }

    /**
     * Returns a string representation of this queue.
     * @return the sequence of items in FIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        Node temp = first;
        while(temp!=null){
            s.append(temp.item + " ");
            temp = temp.next;
        }
        return s.toString();
    }

}

// Driver class

class DriverClass{
   public static void main(String[] args) {
            LinkedQueue<Integer> q = new LinkedQueue<Integer>();
            q.enqueue(3);
            q.enqueue(4);
            q.enqueue(5);
            q.enqueue(6);
            System.out.println(q.toString());
            q.dequeue();
            System.out.println(q.toString());
            q.dequeue();
            System.out.println(q.toString());
            q.enqueue(23);
            System.out.println(q.toString());
          
        }
}

/*

output:

3 4 5 6
4 5 6
5 6
5 6 23

*/

Part2:

import java.util.NoSuchElementException;

/**
   An implementation of a queue as a circular array.
*/
public class CircularArrayQueue
{
   private Object[] elements;
   private int currentSize;
   private int head;
   private int tail;

   /**
      Constructs an empty queue.
   */
   public CircularArrayQueue()
   {
      final int INITIAL_SIZE = 10;
      elements = new Object[INITIAL_SIZE];
      currentSize = 0;
      head = 0;
      tail = 0;
   }

   /**
      Checks whether this queue is empty.
      @return true if this queue is empty
   */
   public boolean empty() { return currentSize == 0; }

   /**
      Adds an element to the tail of this queue.
      @param newElement the element to add
   */
   public void add(Object newElement)
   {
      growIfNecessary();
      currentSize++;
      elements[tail] = newElement;
      tail = (tail + 1) % elements.length;
   }

   /**
      Removes an element from the head of this queue.
      @return the removed element
   */
   public Object remove()
   {
      if (currentSize == 0) { throw new NoSuchElementException(); }
      Object removed = elements[head];
      head = (head + 1) % elements.length;
      currentSize--;
      return removed;
   }

   /**
      Grows the element array if the current size equals the capacity.
   */
   private void growIfNecessary()
   {
      if (currentSize == elements.length)
      {
         Object[] newElements = new Object[2 * elements.length];
         for (int i = 0; i < elements.length; i++)
         {
            newElements[i] = elements[(head + i) % elements.length];
         }    
         elements = newElements;
         head = 0;
         tail = currentSize;
      }
   }

   /**
   * Returns a string representation of this queue.
   *
   * @return the string representation of this queue
   */
   public String toString() {
       String result = "";
       int scan = head;

       while (scan != tail) {
           result += elements[scan].toString() + " ";
           scan = (scan+1) % elements.length;
       }

       return result;
   }
}

//Driver class

class DriverCAQ{
   public static void main(String[] args) {
       CircularArrayQueue caq = new CircularArrayQueue();
       caq.add(12);
       caq.add(13);
       caq.add(14);
       caq.add(15);
       System.out.println(caq.toString());
       caq.remove();
       System.out.println(caq.toString());
      
   }
}

/*

Output:

12 13 14 15
13 14 15

*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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