Java - Dynamic Stack 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:Stacks.ppt
• Dynamic Stack Visualization

Directions

Before & After Visualizations

1. Take out a pencil and paper or a dry-erase board and marker
2. Load the Dynamic Stack 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 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?
     • push(4)
     • push(2)
     • pop()
     • pop()

Dynamic Stack class

1. Create a new project named DynamicStackProject
2. Create a new class called DynamicStack
3. Create a new class called Node
   • Implement the code for the Node class using Media:Node.java as a guide
   • You may want to add a specific constructor that takes in data as a parameter

Attributes

• What attribute must we keep track of when we talk about stacks? (Hint: rhymes with "mop")
• Create a Node reference for the most important stack attribute
  • Do not forget to initialize it to null

Methods

• void push(int data)
  1. push() should not return anything
  2. push() creates a new Node with the data parameter
  3. assign the new Node's next reference to the top (so that the new Node is linked to the current top Node)
  4. update the top to reference the new Node!

• int pop()
  1. pop() returns Integer.MIN_VALUE if the stack is empty
  2. pop() removes the value on top of the stack and returns it
  3. update the top so that it references its next Node (you need to update top before you return the data)

• boolean isEmpty()
  1. return true if the stack is empty, and false otherwise
  2. Hint: What does top reference when the stack is empty?

• void print()
  1. print your entire stack starting at the top (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 stack assignment
2. Write a loop that pushes A LOT of data to test the dynamic size
3. Write a loop that pops A LOT of data to make sure it works too