/**
* 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;
}
}
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;
}
}
import java.util.Random;
/**
* Queue Manager
* 1. "has a" Queue
* 2. support management of Queue tasks (aka: titling, adding a list, printing)
*/
class QueueManagerChanged<T> {
// queue data
private final String name; // name of queue
protected int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
private String lastOperation = "";
private String lastObject = "";
/**
* Queue constructor
* Title with empty queue
*/
public QueueManagerChanged(String name) {
this.name = name;
}
public int getCount() {
return this.count;
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.println(lastOperation + ": " + lastObject);
System.out.print(this.name + " count: " + count);
System.out.print(", data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
public void printIntQueue() {
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
/**
* Add an objects to queue
*/
public void add(T object) { //accepts single generic T Object
this.queue.add(object);
this.count++;
this.lastOperation = "Enqueued";
this.lastObject = object.toString();
}
public LinkedList<T> getHead() {
return this.queue.getHead();
}
public T delete() { //accepts single generic T Object
T headObject = this.queue.delete();
this.count--;
this.lastOperation = "Dequeued";
this.lastObject = headObject.toString();
return headObject;
}
public T peek() { //accepts single generic T Object
return this.queue.peek();
}
public LinkedList<T> getNode(int index) {
LinkedList<T> node = queue.getHead();
for (int i = 0; i < index; i++) {
node = node.getNext();
}
return node;
}
public void shuffle() {
for(LinkedList<T> node1 = queue.getHead(); node1 != null; node1 = node1.getNext()) {
Random random = new Random();
int index = random.nextInt(count);
LinkedList<T> node2 = getNode(index);
T temp = node1.getData();
node1.setData(node2.getData());
node2.setData(temp);
// Swap them
}
}
}
import java.util.*;
public class QueueChangeTester {
public static void main(String[] args) {
// Create an array of strings representing FRQs
Object[] Levels = new String[] { "underground", "forest floor", "understory", "canopy", "emergent", "sky", "space"};
// Create a new QueueManagerChanged object called qFRQs
QueueManagerChanged qLevels = new QueueManagerChanged("Levels");
// Iterate over the FRQs array and add each element to the qFRQs queue
for (Object i : Levels) {
qLevels.add(i);
qLevels.printQueue(); // Print the current state of the queue
}
// Iterate over the FRQs array again and delete each element from the qFRQs queue
for (Object i : Levels) {
qLevels.delete();
qLevels.printQueue(); // Print the current state of the queue
}
}
}
QueueChangeTester.main(null);
class QueueCombine {
public static void main(String[] args) {
// Create three arrays of integers and three queue objects to hold them
Object[] ints1 = new Integer[] { 1, 3, 5, 7};
QueueManagerChanged q1 = new QueueManagerChanged("Queue1");
Object[] ints2 = new Integer[] { 2, 4, 6, 8};
QueueManagerChanged q2 = new QueueManagerChanged("Queue2");
Object[] ints3 = new Integer[] { };
QueueManagerChanged q3 = new QueueManagerChanged("Queue3");
// Add the integers in ints1 to q1
for (Object o : ints1) {
q1.add(o);
}
// Add the integers in ints2 to q2
for (Object o : ints2) {
q2.add(o);
}
// Print the initial state of q1 and q2
System.out.print("Initial Queue First: ");
q1.printIntQueue();
System.out.print("Initial Queue Second: ");
q2.printIntQueue();
// Combine q1 and q2 into q3
while (q1.getCount() != 0 || q2.getCount() != 0) {
// If both q1 and q2 have elements, compare the first elements and add the smaller one to q3
if (q1.getCount() != 0 && q2.getCount() != 0) {
int i1 = (Integer) q1.peek();
int i2 = (Integer) q2.peek();
if (i1 <= i2) {
q3.add(q1.delete());
}
else {
q3.add(q2.delete());
}
}
// If only q1 has elements, add the first element to q3
else if (q1.getCount() != 0) {
q3.add(q1.delete());
}
// If only q2 has elements, add the first element to q3
else if (q2.getCount() !=0) {
q3.add(q2.delete());
}
else {
// Do nothing
}
}
// Print the final state of q3
System.out.print("Final Queue Third: ");
q3.printIntQueue();
}
}
QueueCombine.main(null);
public class QueueShuffle {
public static void main(String[] args) {
// Create an array of integers
Object[] integers = new Integer[] { 1, 2, 3, 4, 5};
// Create a new queue and add the integers to it
QueueManagerChanged qIntegers = new QueueManagerChanged("Numbers");
for (Object i : integers) {
qIntegers.add(i);
}
// Print the original queue
System.out.print("Original Queue:");
qIntegers.printIntQueue();
// Shuffle the queue
qIntegers.shuffle();
// Print the shuffled queue
System.out.print("Queue After Shuffling:");
qIntegers.printIntQueue();
}
}
// Call the main method of the QueueShuffle class
QueueShuffle.main(null);
import java.util.*;
public class ReverseQueue {
public static void main(String[] args) {
Object[] integers = new Integer[] { 1, 2, 3, 4, 5};
QueueManagerChanged qIntegers = new QueueManagerChanged("Numbers");
for (Object o : integers) {
qIntegers.add(o);
}
Stack<Object> stack = new Stack<>();
System.out.println("Stack Initial: " + stack);
System.out.print("Queue Initial: ");
qIntegers.printIntQueue();
// Push all elements from queue to stack
while (qIntegers.getCount() != 0) {
stack.push(qIntegers.delete());
}
System.out.println("Stack Full: " + stack);
System.out.print("Queue when Stacked: ");
qIntegers.printIntQueue();
// Pop all elements from stack and add back to queue
while (stack.size() != 0) {
qIntegers.add(stack.pop());
}
// Print the reversed queue
System.out.println("Stack Final: " + stack);
System.out.print("Queue Final: ");
qIntegers.printIntQueue();
}
}
ReverseQueue.main(null);