Queue Hacks
Jupyter Notebook on data structures hacks
/**
* 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;
}
}
/**
* 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 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;
}
/**
* Get the number of elements in the Queue.
*/
public int size() {
int count = 0;
for (T data : this) {
count++;
}
return count;
}
/*
* Returns true if Queue is empty.
*/
public boolean isEmpty() {
return this.head == null;
}
/**
* Return data in Queue.
*/
public String toString() {
String str = "";
for (T data : this) {
str += data + " ";
}
return str;
}
/**
* Returns data as List.
*/
public List<T> asList() {
List<T> list = new ArrayList<>();
for (T data : this) {
list.add(data);
}
return list;
}
/**
* 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);
}
}
/**
* Queue Manager
* 1. "has a" Queue
* 2. support management of Queue tasks (aka: titling, adding a list, printing)
*/
class QueueManager<T> {
// queue data
private final String name; // name of queue
private int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
/**
* Queue constructor
* Title with empty queue
*/
public QueueManager(String name) {
this.name = name;
}
/**
* Queue constructor
* Title with series of Arrays of Objects
*/
public QueueManager(String name, T[]... seriesOfObjects) {
this.name = name;
this.addList(seriesOfObjects);
}
/**
* Add an element to queue
*/
public void add(T data) {
System.out.println("Enqueued data: " + data);
this.queue.add(data);
this.count++;
}
/**
* Add a list of objects to queue
*/
public void addList(T[]... seriesOfObjects) { //accepts multiple generic T lists
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.queue.add(data);
this.count++;
}
}
/**
* Delete an element from queue
*/
public void delete() {
// print data else print null
System.out.println("Dequeued data: " + this.queue.delete());
this.count--;
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.print(this.name + " count: " + count + ", data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
}
/**
* 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 Words
Object[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
QueueManager qWords = new QueueManager("Words", words);
qWords.printQueue();
// Create iterable Queue of Integers
Object[] numbers = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
QueueManager qNums = new QueueManager("Integers", numbers );
qNums.printQueue();
// // Create iterable Queue of NCS Generics
// Animal.setOrder(Animal.KeyType.name);
// Alphabet.setOrder(Alphabet.KeyType.letter);
// Cupcake.setOrder(Cupcake.KeyType.flavor);
// // Illustrates use of a series of repeating arguments
// QueueManager qGenerics = new QueueManager("My Generics",
// Alphabet.alphabetData(),
// Animal.animals(),
// Cupcake.cupcakes()
// );
// qGenerics.printQueue();
// // Create iterable Queue of Mixed types of data
// QueueManager qMix = new QueueManager("Mixed");
// qMix.queue.add("Start");
// qMix.addList(
// words,
// numbers,
// Alphabet.alphabetData(),
// Animal.animals(),
// Cupcake.cupcakes()
// );
// qMix.queue.add("End");
// qMix.printQueue();
}
}
QueueTester.main(null);
Description
The above code defines a custom implementation of a Queue data structure in Java, which is implemented using a linked list data structure. The Queue class uses a generic type T, which allows it to be used for any type of data.
The QueueIterator class is a private inner class of the Queue class that implements the Iterator interface. The QueueIterator class provides an iterator over the Queue. It has a reference to the current element in the Queue, and the hasNext() method checks if there is another element in the Queue. The next() method returns the data object and advances to the next position in the Queue.
The Queue class has the following methods:
- add(): This method adds a new object to the end of the Queue.
- delete(): This method removes and returns the head object in the Queue.
- peek(): This method returns the data of the head object in the Queue without removing it.
- getHead(): This method returns the head object in the Queue.
- getTail(): This method returns the tail object in the Queue.
- iterator(): This method returns an iterator over the Queue.
- isEmpty(): This method returns a boolean indicating if the Queue is empty.
- toString(): This method returns a string representation of the Queue.
The Queue class uses a linked list to implement the Queue data structure. The head and tail of the Queue are represented by a linked list node. The add() method adds a new node to the end of the linked list, and the delete() method removes the head node of the linked list
Queue<String> queue = new Queue<>();
// Adding elements to the queue
String[] elementsToAdd = {"seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
for (String element : elementsToAdd) {
queue.add(element);
System.out.println("Enqueued data: " + element);
System.out.println(queue.toString());
}
// Deleting elements from the queue
while (!queue.isEmpty()) {
String dequeuedElement = queue.delete();
System.out.println("Dequeued data: " + dequeuedElement);
System.out.println(queue.toString());
}
In this implementation, we first create a new Queue object and an array of elements to add to the queue. We then loop through each element in the array, adding it to the queue using the add method and printing the queue using the toString method after each addition.
After all the elements have been added to the queue, we use a while loop to dequeue elements from the queue until it is empty. Inside the loop, we call the delete method to remove the next element from the queue and print the dequeued element and the updated queue using the toString method. The loop continues until the queue is empty, which is detected using the isEmpty method.
/**
* 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);
//FILO and LILO
public class ShuffleQueue {
public static void main(String[] args) {
Object[] numbers = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
QueueManager<Object> q = new QueueManager<Object>("Numbers", numbers);
q.printQueue();
QueueManager<Object> shuffled = shuffle(q);
shuffled.printQueue();
}
public static QueueManager<Object> shuffle(QueueManager<Object> q) {
// first convert to ArrayList then shuffle
List<Object> list = new ArrayList<Object>(q.queue.asList());
Collections.shuffle(list);
QueueManager<Object> shuffled = new QueueManager<Object>("Shuffled");
shuffled.addList(list.toArray());
return shuffled;
}
}
ShuffleQueue.main(null);
public class ReverseQueue {
public static void main(String[] args) {
Stack<Object> stack = new Stack<Object>();
Object[] numbers = new Integer[] { 1, 2, 3, 4, 5};
QueueManager<Object> q = new QueueManager<Object>("Numbers", numbers);
q.printQueue();
// place elements from Queue into Stack
while (!q.queue.isEmpty()) {
stack.push(q.queue.delete());
}
// place elements from Stack back into Queue
while (!stack.isEmpty()) {
q.queue.add(stack.pop());
}
q.printQueue();
}
}
ReverseQueue.main(null);
public class Stage {
// Class data
// Instance data
private String name;
private String difficulty;
private String question;
/* constructor
*
*/
public Stage(String name, String difficulty, String question)
{
this.name = name;
this.difficulty = difficulty;
this.question = question;
}
@Override
public String toString()
{
return "{ \"name\": \"" + name + "\", \"difficulty\": \"" + difficulty + "\", \"question\": \"" + question + "\" }";
}
// Test data initializer
public static Stage[] stages()
{
return new Stage[] {
new Stage("Jungle Jump", "1", "What data structure uses a LIFO (last in, first out) approach?"),
new Stage("Coconut Climb", "2", "What data structure is made up of a series of nodes, each containing data and a reference to the next node?"),
new Stage("Vine Swing", "3", "What data structure has a hierarchical structure with a root, branches, and leaves?"),
new Stage("Banana Bounce", "4", "What data structure is made up of nodes and edges that connect the nodes?"),
new Stage("Mango Maze", "5", "What data structure is a collection of elements of the same type, accessed by an index or a subscript?"),
new Stage("Papaya Peak", "6", "What data structure uses a hash function to map keys to values, allowing for efficient lookup and insertion?"),
new Stage("Durian Dive", "7", "What data structure is a binary tree with the property that the value of each node is greater than or equal to its children?"),
new Stage("Guava Glide", "8", "What algorithm sorts a list by repeatedly swapping adjacent elements that are in the wrong order?"),
new Stage("Passionfruit Plunge", "9", "What algorithm searches for an element in a sorted list by repeatedly dividing the search interval in half?"),
new Stage("Dragonfruit Dash", "10", "What technique solves a problem by breaking it down into smaller subproblems of the same type?"),
};
}
/* main to test Stage class
*
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
Stage junglejump = new Stage("Jungle Jump", "1", "What data structure uses a LIFO (last in, first out) approach?");
// print with title
System.out.println("Stage Class Test");
System.out.println(junglejump.toString());
}
}
class StageStackTester {
public static void main(String[] args) {
Stack<Stage> s = new Stack<>();
for (Stage p : Stage.stages()) {
s.add(p);
}
System.out.println(s);
}
}
StageStackTester.main(null);