Linked List Code

/**
 *  Implementation of a Double Linked List;  forward and backward links point to adjacent Nodes.
 *
 */

 public class LinkedList<T>
 {
     private T data;
     private LinkedList<T> prevNode, nextNode;
 
     /**
      *  Constructs a new element
      *
      * @param  data, data of object
      * @param  node, previous node
      */
     public LinkedList(T data, LinkedList<T> node)
     {
         this.setData(data);
         this.setPrevNode(node);
         this.setNextNode(null);
     }
 
     /**
      *  Clone an object,
      *
      * @param  node  object to clone
      */
     public LinkedList(LinkedList<T> node)
     {
         this.setData(node.data);
         this.setPrevNode(node.prevNode);
         this.setNextNode(node.nextNode);
     }
 
     /**
      *  Setter for T data in DoubleLinkedNode object
      *
      * @param  data, update data of object
      */
     public void setData(T data)
     {
         this.data = data;
     }
 
     /**
      *  Returns T data for this element
      *
      * @return  data associated with object
      */
     public T getData()
     {
         return this.data;
     }
 
     /**
      *  Setter for prevNode in DoubleLinkedNode object
      *
      * @param node, prevNode to current Object
      */
     public void setPrevNode(LinkedList<T> node)
     {
         this.prevNode = node;
     }
 
     /**
      *  Setter for nextNode in DoubleLinkedNode object
      *
      * @param node, nextNode to current Object
      */
     public void setNextNode(LinkedList<T> node)
     {
         this.nextNode = node;
     }
 
 
     /**
      *  Returns reference to previous object in list
      *
      * @return  the previous object in the list
      */
     public LinkedList<T> getPrevious()
     {
         return this.prevNode;
     }
 
     /**
      *  Returns reference to next object in list
      *
      * @return  the next object in the list
      */
     public LinkedList<T> getNext()
     {
         return this.nextNode;
     }
 
 }

Queue Base Code

import java.util.Iterator;

/**
 * Queue Iterator
 *
 * 1. "has a" current reference in Queue
 * 2. supports iterable required methods for next that returns a generic T Object
 */
class QueueIterator<T> implements Iterator<T> {
    LinkedList<T> current;  // current element in iteration

    // QueueIterator is pointed to the head of the list for iteration
    public QueueIterator(LinkedList<T> head) {
        current = head;
    }

    // hasNext informs if next element exists
    public boolean hasNext() {
        return current != null;
    }

    // next returns data object and advances to next position in queue
    public T next() {
        T data = current.getData();
        current = current.getNext();
        return data;
    }
}

/**
 * Queue: custom implementation
 * @author     John Mortensen
 *
 * 1. Uses custom LinkedList of Generic type T
 * 2. Implements Iterable
 * 3. "has a" LinkedList for head and tail
 */
public class Queue<T> implements Iterable<T> {
    LinkedList<T> head = null, tail = null;

    /**
     *  Add a new object at the end of the Queue,
     *
     * @param  data,  is the data to be inserted in the Queue.
     */
    public void add(T data) {
        // add new object to end of Queue
        LinkedList<T> tail = new LinkedList<>(data, null);

        if (this.head == null)  // initial condition
            this.head = this.tail = tail;
        else {  // nodes in queue
            this.tail.setNextNode(tail); // current tail points to new tail
            this.tail = tail;  // update tail
        }
    }

    /**
     *  Returns the data of head.
     *
     * @return  data, the dequeued data
     */
    public T delete() {
        T data = this.peek();
        if (this.tail != null) { // initial condition
            this.head = this.head.getNext(); // current tail points to new tail
            if (this.head != null) {
                this.head.setPrevNode(tail);
            }
        }
        return data;
    }

    /**
     *  Returns the data of head.
     *
     * @return  this.head.getData(), the head data in Queue.
     */
    public T peek() {
        return this.head.getData();
    }

    /**
     *  Returns the head object.
     *
     * @return  this.head, the head object in Queue.
     */
    public LinkedList<T> getHead() {
        return this.head;
    }

    /**
     *  Returns the tail object.
     *
     * @return  this.tail, the last object in Queue
     */
    public LinkedList<T> getTail() {
        return this.tail;
    }

    /**
     *  Returns the iterator object.
     *
     * @return  this, instance of object
     */
    public Iterator<T> iterator() {
        return new QueueIterator<>(this.head);
    }

    /**
     * Returns if queue is empty
     * 
     * @return boolean if it is empty
     */
    public boolean isEmpty() {
      return this.head == null;
    }
    
    public String toString() {
      int count = 0;
      String str = "";
      for (T e : this) {
        str += e + " ";
        count++;
      }
      return "Words count: " + count + ", data: " + str;
    }
}

Challenge 1

Add and Delete elements from Queue. Working with the code that is given, you will need to adjust Add and write Delete, to output from the Queue as follows

/**
 * Driver Class
 * Tests queue with string, integers, and mixes of Classes and types
 */
class QueueTester {
    public static void main(String[] args)
    {
        // Create iterable Queue of Levels
        String[] levels = new String[] { "underground", "forest floor", "understory", "canopy", "emergent", "sky", "space"};
        Queue<String> q = new Queue<>();
        for (String w : levels) {
          q.add(w);
          System.out.println("Enqueued Data: " + w);
          System.out.println(q);
        }
  
        while (!q.isEmpty()) {
          String val = q.delete();
          System.out.println("Dequeued Data: " + val);
          System.out.println(q);
        }
    }
  }
  QueueTester.main(null);

Enqueued Data: underground
Words count: 1, data: underground 
Enqueued Data: forest floor
Words count: 2, data: underground forest floor 
Enqueued Data: understory
Words count: 3, data: underground forest floor understory 
Enqueued Data: canopy
Words count: 4, data: underground forest floor understory canopy 
Enqueued Data: emergent
Words count: 5, data: underground forest floor understory canopy emergent 
Enqueued Data: sky
Words count: 6, data: underground forest floor understory canopy emergent sky 
Enqueued Data: space
Words count: 7, data: underground forest floor understory canopy emergent sky space 
Dequeued Data: underground
Words count: 6, data: forest floor understory canopy emergent sky space 
Dequeued Data: forest floor
Words count: 5, data: understory canopy emergent sky space 
Dequeued Data: understory
Words count: 4, data: canopy emergent sky space 
Dequeued Data: canopy
Words count: 3, data: emergent sky space 
Dequeued Data: emergent
Words count: 2, data: sky space 
Dequeued Data: sky
Words count: 1, data: space 
Dequeued Data: space
Words count: 0, data:

Challenge 2

Perform a merge or combination of 2 Queue's that are ordered. This is a foundation step for the algorithm used in Merge sorting.

/**
 * Driver Class
 * Tests queue with string, integers, and mixes of Classes and types
 */
class QueueTester2 {
    public static void main(String[] args)
    {
        // Create first queue
        int[] firstData = {1, 4, 5, 8};
        Queue<Integer> firstQ = new Queue<>();
        for (int i : firstData) {
          firstQ.add(i);
        }
  
        // Create second queue
        int[] secondData = {2, 3, 6, 7};
        Queue<Integer> secondQ = new Queue<>();
        for (int i : secondData) {
          secondQ.add(i);
        }
  
        System.out.println("First Queue");
        System.out.println(firstQ);
        System.out.println("Second Queue");
        System.out.println(secondQ);
  
        // Merge the queues
        Queue<Integer> mergedQ = new Queue<>();
        while (!firstQ.isEmpty() || !secondQ.isEmpty()) {
          if (firstQ.isEmpty()) {
            mergedQ.add(secondQ.delete());
          }
          else if (secondQ.isEmpty()) {
            mergedQ.add(firstQ.delete());
          }
          else if (firstQ.peek() < secondQ.peek()) {
            mergedQ.add(firstQ.delete());
          }
          else {
            mergedQ.add(secondQ.delete());
          }
        }
  
        System.out.println("Merged Queue");
        System.out.println(mergedQ);
    }
  }
  QueueTester2.main(null);

First Queue
Words count: 4, data: 1 4 5 8 
Second Queue
Words count: 4, data: 2 3 6 7 
Merged Queue
Words count: 8, data: 1 2 3 4 5 6 7 8

Challenge 3

Shuffle the Queue. Iterate through the Queue and change data with another random position in the queue.

class QueueShuffler<T> {
    public void shuffle(Queue<T> q) {
        List<T> dequeuedQueue = new ArrayList<>();
        
        while (!q.isEmpty()) {
          dequeuedQueue.add(q.delete());
        }
    
        while (!dequeuedQueue.isEmpty()) {
          int rand = (int) (Math.random() * dequeuedQueue.size());
          q.add(dequeuedQueue.get(rand));
          dequeuedQueue.remove(rand);
        }
    }
}

/**
 * Driver Class
 * Tests queue with string, integers, and mixes of Classes and types
 */
class QueueTester3 {
    public static void main(String[] args)
    {
      
      // Create first queue
      int[] firstData = {1, 2,3,4,5,6,7,8};
      Queue<Integer> firstQ = new Queue<>();
      for (int i : firstData) {
        firstQ.add(i);
      }
  
      System.out.println(firstQ);
  
      QueueShuffler<Integer> shuffler = new QueueShuffler<>();
      shuffler.shuffle(firstQ);
      
      System.out.println(firstQ);
  
    }
  }
  QueueTester3.main(null);

Words count: 8, data: 1 2 3 4 5 6 7 8 
Words count: 8, data: 1 4 8 7 3 6 2 5

Challenge 4

Build a Stack and use it to reverse the order of a Queue. The Queue is a LIFO Data Structure, the Stack is a FIFO data structure, so code is similar but most everything is reversed.

import java.util.Iterator;

/**
 * Queue Iterator
 *
 * 1. "has a" current reference in Queue
 * 2. supports iterable required methods for next that returns a generic T Object
 */
class StackIterator<T> implements Iterator<T> {
    LinkedList<T> current;  // current element in iteration

    // QueueIterator is pointed to the head of the list for iteration
    public StackIterator(LinkedList<T> head) {
        current = head;
    }

    // hasNext informs if next element exists
    public boolean hasNext() {
        return current != null;
    }

    // next returns data object and advances to next position in queue
    public T next() {
        T data = current.getData();
        current = current.getNext();
        return data;
    }
}

/**
 * Queue: custom implementation
 * @author     John Mortensen
 *
 * 1. Uses custom LinkedList of Generic type T
 * 2. Implements Iterable
 * 3. "has a" LinkedList for head and tail
 */
public class Stack<T> implements Iterable<T> {
    LinkedList<T> head = null, tail = null;

    /**
     *  Add a new object at the end of the Queue,
     *
     * @param  data,  is the data to be inserted in the Queue.
     */
    public void add(T data) {
        // add new object to end of Queue
        LinkedList<T> head = new LinkedList<>(data, null);

        if (this.head == null)  // initial condition
            this.head = this.tail = head;
        else {  // nodes in queue
            head.setNextNode(this.head);
            this.head = head;  // update head
        }
    }

    /**
     *  Returns the data of head.
     *
     * @return  data, the dequeued data
     */
    public T delete() {
        T data = this.peek();
        if (this.tail != null) { // initial condition
            this.head = this.head.getNext(); // current tail points to new tail
            if (this.head != null) {
                this.head.setPrevNode(tail);
            }
        }
        return data;
    }

    /**
     *  Returns the data of head.
     *
     * @return  this.head.getData(), the head data in Queue.
     */
    public T peek() {
        return this.head.getData();
    }

    /**
     *  Returns the head object.
     *
     * @return  this.head, the head object in Queue.
     */
    public LinkedList<T> getHead() {
        return this.head;
    }

    /**
     *  Returns the tail object.
     *
     * @return  this.tail, the last object in Queue
     */
    public LinkedList<T> getTail() {
        return this.tail;
    }

    /**
     *  Returns the iterator object.
     *
     * @return  this, instance of object
     */
    public Iterator<T> iterator() {
        return new QueueIterator<>(this.head);
    }

    /**
     * Returns if queue is empty
     * 
     * @return boolean if it is empty
     */
    public boolean isEmpty() {
      return this.head == null;
    }
    
    public String toString() {
      int count = 0;
      String str = "";
      for (T e : this) {
        str += e + " ";
        count++;
      }
      return "Words count: " + count + ", data: " + str;
    }
}

/**
 * Driver Class
 * Tests queue with string, integers, and mixes of Classes and types
 */
class StackTester {
    public static void main(String[] args)
    {
        int[] data = {1, 2, 3};
        Queue<Integer> q = new Queue<>();
        for (int i : data) {
          q.add(i);
        }
        System.out.println("Queue");
        System.out.println(q);
  
        // use stack
        Stack<Integer> s = new Stack<>();
        while (!q.isEmpty()) {
          s.add(q.delete());
        }
        System.out.println("Stack");
        System.out.println(s);
    }
  }
  StackTester.main(null);

Queue
Words count: 3, data: 1 2 3 
Stack
Words count: 3, data: 3 2 1