Queue Notes
what is gpt?
- Linked List code
- Queue Base Code
- Notes on Code
- 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.
- 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.
- Challenge 3
- Challenge 4
- Stack with custom data type
/**
* 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;
}
}
Notes on Code
Managing data in the Queue
There were modifications done to the code, mostly to remove the QueueManager class. The QueueManager class simply creates a Queue object while taking in an array of objects, which could be useful but is kind of unneccessary when one can use the enhanced for loop. Instead, the add method can be called, and this manipulation of data can be seen in the challenges below.
ForEach and Iterables
The code seen here:
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
Is in the Queue class, and this is called when an enhanced for loop is called. It returns an iterator, which is an object that can be used to iterate over a collection. The QueueIterator class is defined as follows:
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;
}
}
It is able to check if there is a next element, and it is able to return the next element. This is what allows the enhanced for loop to work, and it is what allows the Queue to be iterable.
This also works for Generic data, as the generic type of T is used in the Queue classes. Thus, it can take any type of data, as long as it has a comparable interface. For example, as seen in the challenge below, it can take a String, an Integer, or a Double.
/**
* 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
String[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
Queue<String> q = new Queue<>();
for (String w : words) {
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);
/**
* 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);
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);
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);
public class Person {
// Class data
// Instance data
private String name;
private String email;
private String passwordHash;
/* constructor
*
*/
public Person(String name, String email, String passwordHash)
{
this.name = name;
this.email = email;
this.passwordHash = passwordHash;
}
@Override
public String toString()
{
return "{ \"Name\": \"" + name + "\", \"Email\": \"" + email + "\", \"Password\": \"" + passwordHash + "\" }";
}
// Test data initializer
public static Person[] persons()
{
return new Person[] {
new Person("John", "john@email.com", "password"),
new Person("Mary", "mary@email.com", "password2"),
new Person("Bob", "bob@email.com", "password3")
};
}
/* main to test Person class
*
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
//Person[] objs = persons();
Person john = new Person("John", "john@email.com", "password");
// print with title
System.out.println("Person Class Test");
System.out.println(john.toString());
}
}
class PersonStackTester {
public static void main(String[] args) {
Stack<Person> s = new Stack<>();
for (Person p : Person.persons()) {
s.add(p);
}
System.out.println(s);
}
}
PersonStackTester.main(null);