Difference between revisions of "Java - Dynamic Stack Assignment"
From WLCS
(7 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
== Objectives == | == Objectives == | ||
− | * You will implement a dynamically-sized | + | * You will implement a dynamically-sized stack using linked Nodes |
− | * You will implement | + | * You will implement stack methods (push(), pop(), isEmpty(), etc.) |
− | * You will test your dynamic | + | * You will test your dynamic stack in a main() method |
== Resources == | == Resources == | ||
* [[Media:Stacks.ppt]] | * [[Media:Stacks.ppt]] | ||
− | * | + | * [https://www.cs.usfca.edu/~galles/visualization/StackLL.html Dynamic Stack Visualization] |
== Directions == | == Directions == | ||
Line 21: | Line 21: | ||
#** pop() | #** pop() | ||
− | === | + | === Node class === |
− | # Create a new | + | # 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 === | ||
# Create a new class called DynamicStack | # Create a new class called DynamicStack | ||
− | # Create a | + | # Create a default constructor for a DynamicStack |
− | # | + | # Implement the following attributes and methods: |
− | |||
==== Attributes ==== | ==== Attributes ==== | ||
Line 41: | Line 44: | ||
* '''int pop()''' | * '''int pop()''' | ||
− | *# pop() returns | + | *# pop() returns Integer.MIN_VALUE if the stack is empty |
*# pop() removes the value on top of the stack and returns it | *# pop() removes the value on top of the stack and returns it | ||
*# update the '''top''' so that it references its next Node (you need to update top before you return the data) | *# update the '''top''' so that it references its next Node (you need to update top before you return the data) | ||
+ | |||
+ | * '''int top()''' | ||
+ | *# return the value at the top of the stack | ||
+ | *# return Integer.MIN_VALUE if the stack is empty | ||
* '''boolean isEmpty()''' | * '''boolean isEmpty()''' | ||
*# return true if the stack is empty, and false otherwise | *# return true if the stack is empty, and false otherwise | ||
*# Hint: What does '''top''' reference when the stack is empty? | *# Hint: What does '''top''' reference when the stack is empty? | ||
+ | |||
+ | * '''String toString()''' | ||
+ | *# Use a loop to generate the String version of your stack's data | ||
+ | *# return the String | ||
* '''void print()''' | * '''void print()''' | ||
− | *# print your entire stack | + | *# print your entire stack starting at the '''top''' (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 stack assignment | |
− | + | # Write a loop that pushes A LOT of data to test the dynamic stack | |
+ | # Print the stack | ||
+ | # Write a loop that pops A LOT of data to make sure it works too | ||
+ | # Print the stack (it should be empty now) |
Latest revision as of 15:19, 15 November 2016
Contents
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
Directions
Before & After Visualizations
- Take out a pencil and paper or a dry-erase board and marker
- Load the 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?
- push(4)
- push(2)
- pop()
- pop()
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
DynamicStack class
- Create a new class called DynamicStack
- Create a default constructor for a DynamicStack
- 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)
- push() should not return anything
- push() creates a new Node with the data parameter
- assign the new Node's next reference to the top (so that the new Node is linked to the current top Node)
- update the top to reference the new Node!
- int pop()
- pop() returns Integer.MIN_VALUE if the stack is empty
- pop() removes the value on top of the stack and returns it
- update the top so that it references its next Node (you need to update top before you return the data)
- int top()
- return the value at the top of the stack
- return Integer.MIN_VALUE if the stack is empty
- boolean isEmpty()
- return true if the stack is empty, and false otherwise
- Hint: What does top reference when the stack is empty?
- String toString()
- Use a loop to generate the String version of your stack's data
- return the String
- void print()
- print your entire stack starting at the top (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 stack assignment
- Write a loop that pushes A LOT of data to test the dynamic stack
- Print the stack
- Write a loop that pops A LOT of data to make sure it works too
- Print the stack (it should be empty now)