Java - Dynamic Stack Assignment

Objectives

• You will implement a dynamically-sized stack using linked Nodes
• You will implement stack methods (push(), pop(), isEmpty(), etc.)
• You will test your dynamic stack 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()

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

DynamicStack class

1. Create a new class called DynamicStack
2. Create a default constructor for a DynamicStack
3. Implement the following attributes and methods:

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)

• int top()
  1. return the value at the top of the stack
  2. return Integer.MIN_VALUE if the stack is empty

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

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

• 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 stack
3. Print the stack
4. Write a loop that pops A LOT of data to make sure it works too
5. Print the stack (it should be empty now)