Java - Dynamic Queue Assignment - Revision history

Admin at 14:58, 27 November 2017

2017-11-27T14:58:36Z

Admin at 02:55, 16 November 2016

2016-11-16T02:55:58Z

Admin at 19:34, 15 November 2016

2016-11-15T19:34:27Z

Admin at 19:34, 15 November 2016

2016-11-15T19:34:01Z

Admin at 19:33, 15 November 2016

2016-11-15T19:33:01Z

Admin: Created page with "== Objectives == * You will implement a dynamically-sized queue using linked Nodes * You will implement queue methods (enqueue/add, dequeue/remove, etc.) * You will test your..."

2016-11-15T19:27:03Z

Created page with "== Objectives == * You will implement a dynamically-sized queue using linked Nodes * You will implement queue methods (enqueue/add, dequeue/remove, etc.) * You will test your..."

New page

== Objectives ==
* You will implement a dynamically-sized queue using linked Nodes
* You will implement queue methods (enqueue/add, dequeue/remove, etc.)
* You will test your dynamic queue in a main() method

== Resources ==
* [[Media:Queues.ppt]]
* [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Stack Visualization]

== Directions ==

=== Before & After Visualizations ===
# Take out a pencil and paper or a dry-erase board and marker
# Load the [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Stack Visualization]
# Consider each of the following questions and use the visualization tool to help you answer them. Practice drawing each of the visualizations yourself.
#* What does an empty stack look like? (The top reference variable is null)
#* For each of the following actions, assess what the picture looks like Before? then After? What changes occurred to make the Before image become the After image?
#** enqueue(4) # notice what happens to both head and tail!
#** enqueue(2)
#** dequeue()
#** dequeue() # notice what happens to both head and tail!

=== Node class ===
# Create a new class called Node
#* Implement the code for the Node class using [[Media:Node.java]] as a guide
#* You will want to add a specific constructor that takes in data as a parameter, and saves the data into the num attribute

=== DynamicQueue class ===
# Create a new class called DynamicQueue
# Create a default constructor for a DynamicQueue
# Implement the following attributes and methods:

==== Attributes ====
* What attributes must we keep track of when we talk about queues?
* Create two Node references for the queue attributes
** Do not forget to initialize them to '''null'''

==== Methods ====
* '''void enqueue(int data)'''
*# enqueue() creates a new Node with the data parameter at the '''tail''' of the queue
*# enqueue() should not return anything
*# update the '''tail''' to reference the new Node!
*# SPECIAL CASE ALERT! If you add to an empty queue, then the head must change too

# '''void add(int data)'''
*# same as enqueue()

* '''int dequeue()'''
*# pop() returns Integer.MIN_VALUE if the queue is empty
*# pop() removes the value from the head of the queue returns it
*# update the '''head''' so that it references its next Node (you need to update head before you return the data)
*# SPECIAL CASE ALERT! If you remove from the queue when the head is referencing the same tail Node, then there is only one Node left, and the tail must change too

# '''void remove()'''
*# same as dequeue()

* '''int getHead()'''
*# return the value at the head of the queue
*# return Integer.MIN_VALUE if the queue is empty

* '''int getTail()'''
*# return the value at the tail of the queue
*# return Integer.MIN_VALUE if the queue is empty

* '''boolean isEmpty()'''
*# return true if the queue is empty, and false otherwise

* '''String toString()'''
*# Use a loop to generate the String version of your queue's data
*# return the String

* '''void print()'''
*# print your entire queue starting at the '''head''' (to null)
*# Hint: use the for loop that we covered in class

=== Testing ===
# You should be able to reuse your main() method from the static queue assignment
# Write a loop that adds A LOT of data to test the dynamic queue
# Print the queue
# Write a loop that removes A LOT of data to make sure it works too
# Print the queue (it should be empty now)

@@ Line 52: / Line 52: @@
 *# SPECIAL CASE ALERT! If you remove from the queue when the head is referencing the same tail Node, then there is only one Node left, and the tail must change too
-* '''void remove()'''
+* '''int remove()'''
 *# same as dequeue()

@@ Line 47: / Line 47: @@
 * '''int dequeue()'''
-*# pop() returns Integer.MIN_VALUE if the queue is empty
+*# dequeue() returns Integer.MIN_VALUE if the queue is empty
-*# pop() removes the value from the head of the queue returns it
+*# dequeue() removes the value from the head of the queue returns it
 *# update the '''head''' so that it references its next Node (you need to update head before you return the data)
 *# SPECIAL CASE ALERT! If you remove from the queue when the head is referencing the same tail Node, then there is only one Node left, and the tail must change too

@@ Line 14: / Line 14: @@
 # Load the [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Queue Visualization]
 # Consider each of the following questions and use the visualization tool to help you answer them. Practice drawing each of the visualizations yourself.
-#* What does an empty stack look like? (The top reference variable is null)
+#* What does an empty queue look like? (The head and tail reference variables are null)
 #* For each of the following actions, assess what the picture looks like Before? then After? What changes occurred to make the Before image become the After image?
 #** enqueue(4)  # notice what happens to both head and tail!

@@ Line 6: / Line 6: @@
 == Resources ==
 * [[Media:Queues.ppt]]
-* [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Stack Visualization]
+* [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Queue Visualization]
 == Directions ==
@@ Line 12: / Line 12: @@
 === Before & After Visualizations ===
 # Take out a pencil and paper or a dry-erase board and marker
-# Load the [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Stack Visualization]
+# Load the [https://www.cs.usfca.edu/~galles/visualization/QueueLL.html Dynamic Queue Visualization]
 # Consider each of the following questions and use the visualization tool to help you answer them. Practice drawing each of the visualizations yourself.
 #* What does an empty stack look like? (The top reference variable is null)

@@ Line 43: / Line 43: @@
 *# SPECIAL CASE ALERT! If you add to an empty queue, then the head must change too
-# '''void add(int data)'''
+* '''void add(int data)'''
 *# same as enqueue()
@@ Line 52: / Line 52: @@
 *# SPECIAL CASE ALERT! If you remove from the queue when the head is referencing the same tail Node, then there is only one Node left, and the tail must change too
-# '''void remove()'''
+* '''void remove()'''
 *# same as dequeue()