Challenge 1
Generics Types Checkpoint 2 Notes and Hack 1
Stacks
- Stack of bowls analogy
- You can see and take the top bowl and see inside the top of the bowl
- You can't see inside any of the bowls
- You can't easily pull something out of bowls in the middle
- Push (value): add a value to the stack 0(1)
- Pop (value): remove a value from the stack 0(1)
- Peek (value): look at the value on the top of the stack 0(1)
- If we need to store or reverse a bunch of data, it can be done easily
- If you want to reverse a value of a string, you can put them in a stack and push and pop the characters out
- Processing a bunch of data and want to prioritize recent data --> put the data in the stack and you always look at the most recent data you received
Queues
- If you go to the DMV or shop in the grocery store, you have to get into the line or the "queue"
- You enter one side of the line and the work happens at the end of the line
- Add data at the end and remove data at the front of the queue
- We need to process a bunch of data and we need to do it in an order
- Structured and efficient
- enqueue (value): add a value to the queue
- value dequeue(): removes a value from the queue
Linked List
- similar to dynamic array
- keep a bunch of data in a particular order (may not be sorted)
- doesn't have an array; it has a chain of values
- Node: simple object with a value and a next reference where the next node is in the chain
- Linked List uses node so it only has space for how much it needs
- Doesn't have to waste a lot of space
- head points to the first item in linked list and tail that points to the last item
- add nodes to the head
- we only have direct access to the first and last node
- retrieving data means we have to start at the beginning and iterate through until we get to the data place we want
- add (value): add a value to the end; add values to the tail
- value get (index): retrieve a value from the linked list
- remove (index): remove a value at a particular index
- insert (index, value): insert a value at the particular index
- int size: retreive the number of items in a linked list
- remove and add values from the front of the linked list very easily
/**
* 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;
}
}
Implementing Linked List
- Defines class named LinkedList
- Doubly linked list is a type of linked list in which each element (node) of the list contains a reference to the next and previous element in the list
- Three private instances called data, prevNode, and next Node --> element in current, past, and future node
- Three constructors --> 2 take the linked list object as an input and creates a new node with specific data, 1 takes an existing obkect and creates a new node with the same data and reference and reference as the input
- Lots of setters and getters like setData and getData and setPrevNode
/**
* 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 Iterator
- QueueIterator class implements the Iterator interface and provides implementation for the has Next and next methods
- Queue class has many methods like add(), delete(), size(), isEmpty (), etc.
- add() adds an element to the end of the queue, delete() removes element at the head, peek() returns the data at the head without removing it, size() returns the number of elements in the queue, etc.
/**
* 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();
}
}
Queue Manager
- Constructor QueueManager (name, seriesOfObjects) - creates a new QueueManager object with a specified name and a queue intialized with a series of arrays of objects
- add(data): adds an element of type T to the end of the queue
- addList(seriesOfObjects) - adds a list of objects to the end of the queue
- delete() - deletes the element at the front of queue
- printQueue() - prints the contents of the queue
/**
* 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);
public class QueueTester {
public static void main(String[] args) {
QueueManager qWords = new QueueManager("Words");
Object[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
for (Object word : words) {
qWords.add(word); // adds values
qWords.printQueue();
}
for (int i = 0; i < words.length; i++) {
qWords.delete(); // deletes values
qWords.printQueue();
}
// for (Object word : words) {
// System.out.println("Enqueued data: " + word);
// q.add((String) word);
// // print words count and data
// System.out.println("Words count: " + q.size() + ", data: " + q.toString());
// }
}
}
QueueTester.main(null);
Code explained
- defines method a "QueueTester" that tests the functionality of a QueueManager class.
- "qWords" is created with the name "words" which is basically an array of String objects
- For loop: adds each word from the "words" array to the queue by calling the "add" method of the "qWords" object
- 2nd for loop deletes each element from the queue by calling the "delete" method of the "qWords" object, and then prints out the current state of the queue using the "printQueue" method of the "qWords" object
- "main" method tests the QueueManager class by adding and deleting elements from the queue and printing out the state of the queue after each operation
- queue extends and shortens as elements are added and removed