Queues and Stacks
hacks
/* This is wrapper class...
Objective would be to push more functionality into this Class to enforce consistent definition
*/
public abstract class Generics {
public final String masterType = "Generic";
private String type; // extender should define their data type
// generic enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// static print method used by extended classes
public static void print(Generics[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Generics' properties
if (objs.length > 0) {
Generics obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Generics: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Alphabet extends Generics {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Alphabet.key = key;}
public enum KeyType implements KeyTypes {title, letter}
private static final int size = 26; // constant used in data initialization
// Instance data
private final char letter;
/*
* single letter object
*/
public Alphabet(char letter)
{
this.setType("Alphabet");
this.letter = letter;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Alphabet.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString()
{
String output="";
if (KeyType.letter.equals(this.getKey())) {
output += this.letter;
} else {
output += super.getType() + ": " + this.letter;
}
return output;
}
// Test data initializer for upper case Alphabet
public static Alphabet[] alphabetData()
{
Alphabet[] alphabet = new Alphabet[Alphabet.size];
for (int i = 0; i < Alphabet.size; i++)
{
alphabet[i] = new Alphabet( (char)('A' + i) );
}
return alphabet;
}
/*
* main to test Animal class
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
Alphabet[] objs = alphabetData();
// print with title
Alphabet.setOrder(KeyType.title);
Alphabet.print(objs);
// print letter only
Alphabet.setOrder(KeyType.letter);
Alphabet.print(objs);
}
}
Alphabet.main(null);
/*
* Animal class extends Generics and defines abstract methods
*/
public class Animal extends Generics {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) { Animal.key = key; }
public enum KeyType implements KeyTypes {title, name, age, color}
// Instance data
private final String name;
private final int age;
private final String color;
/* constructor
*
*/
public Animal(String name, int age, String color)
{
super.setType("Animal");
this.name = name;
this.age = age;
this.color = color;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Animal.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString()
{
String output="";
if (KeyType.name.equals(this.getKey())) {
output += this.name;
} else if (KeyType.age.equals(this.getKey())) {
output += "00" + this.age;
output = output.substring(output.length() - 2);
} else if (KeyType.color.equals(this.getKey())) {
output += this.color;
} else {
output += super.getType() + ": " + this.name + ", " + this.color + ", " + this.age;
}
return output;
}
// Test data initializer
public static Animal[] animals() {
return new Animal[]{
new Animal("Lion", 8, "Gold"),
new Animal("Pig", 3, "Pink"),
new Animal("Robin", 7, "Red"),
new Animal("Cat", 10, "Black"),
new Animal("Kitty", 1, "Calico"),
new Animal("Dog", 14, "Brown")
};
}
/* main to test Animal class
*
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
Animal[] objs = animals();
// print with title
Animal.setOrder(KeyType.title);
Animal.print(objs);
// print name only
Animal.setOrder(KeyType.name);
Animal.print(objs);
}
}
Animal.main(null);
public class Cupcake extends Generics {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Cupcake.key = key;}
public enum KeyType implements KeyTypes {title, flavor, frosting, sprinkles}
// Instance data
private final String frosting;
private final int sprinkles;
private final String flavor;
// Constructor
Cupcake(String frosting, int sprinkles, String flavor)
{
this.setType("Cupcake");
this.frosting = frosting;
this.sprinkles = sprinkles;
this.flavor = flavor;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Cupcake.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output="";
if (KeyType.flavor.equals(this.getKey())) {
output += this.flavor;
} else if (KeyType.frosting.equals(this.getKey())) {
output += this.frosting;
} else if (KeyType.sprinkles.equals(this.getKey())) {
output += "00" + this.sprinkles;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.flavor + ", " + this.frosting + ", " + this.sprinkles;
}
return output;
}
// Test data initializer
public static Cupcake[] cupcakes() {
return new Cupcake[]{
new Cupcake("Red", 4, "Red Velvet"),
new Cupcake("Orange", 5, "Orange"),
new Cupcake("Yellow", 6, "Lemon"),
new Cupcake("Green", 7, "Apple"),
new Cupcake("Blue", 8, "Blueberry"),
new Cupcake("Purple", 9, "Blackberry"),
new Cupcake("Pink", 10, "Strawberry"),
new Cupcake("Tan", 11, "Vanilla"),
new Cupcake("Brown", 12, "Chocolate"),
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Cupcake[] objs = cupcakes();
// print with title
Cupcake.setOrder(KeyType.title);
Cupcake.print(objs);
// print flavor only
Cupcake.setOrder(KeyType.flavor);
Cupcake.print(objs);
}
}
Cupcake.main(null);
/**
* 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);
}
}
/**
* 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 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++;
}
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.println(this.name + " count: " + count);
System.out.print(this.name + " data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
}
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[] FRQs = new String[] { "2021 Question 1", "2019 Question 2", "2020 Question 3", "2003 Question 4", "2016 Question 3", "2018 Question 2", "2005 Question 1"};
// Create a new QueueManagerChanged object called qFRQs
QueueManagerChanged qFRQs = new QueueManagerChanged("FRQs");
// Iterate over the FRQs array and add each element to the qFRQs queue
for (Object i : FRQs) {
qFRQs.add(i);
qFRQs.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 : FRQs) {
qFRQs.delete();
qFRQs.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);