Java - Dynamic Queue Assignment

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
• Dynamic Queue Visualization

Directions

Before & After Visualizations

1. Take out a pencil and paper or a dry-erase board and marker
2. Load the Dynamic Queue Visualization
3. 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 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!
     • enqueue(2)
     • dequeue()
     • dequeue() # notice what happens to both head and tail!

Node class

1. 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

1. Create a new class called DynamicQueue
2. Create a default constructor for a DynamicQueue
3. 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)
  1. enqueue() creates a new Node with the data parameter at the tail of the queue
  2. enqueue() should not return anything
  3. update the tail to reference the new Node!
  4. SPECIAL CASE ALERT! If you add to an empty queue, then the head must change too

• void add(int data)
  1. same as enqueue()

• int dequeue()
  1. dequeue() returns Integer.MIN_VALUE if the queue is empty
  2. dequeue() removes the value from the head of the queue returns it
  3. update the head so that it references its next Node (you need to update head before you return the data)
  4. 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

• int remove()
  1. same as dequeue()

• int getHead()
  1. return the value at the head of the queue
  2. return Integer.MIN_VALUE if the queue is empty

• int getTail()
  1. return the value at the tail of the queue
  2. return Integer.MIN_VALUE if the queue is empty

• boolean isEmpty()
  1. return true if the queue is empty, and false otherwise

• String toString()
  1. Use a loop to generate the String version of your queue's data
  2. return the String

• void print()
  1. print your entire queue starting at the head (to null)
  2. Hint: use the for loop that we covered in class

Testing

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