Week-02 | Stacks
About
Objective:The purpose of this exercise is to create a "Stack" LIFO data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results of using the library features should be identical with your own version (My API). However, the underlying implementation should follow with the descriptions listed below.
Testing your skills.
Now that you have tested your data structure making strategies. You have already been introduced to Stacks in Practice It, now you will design and implement your own Stack and Queue data structures.
Instructions: Create a Stack class using "singly linked" data structures. NOTE: This isnotsaying the implementation is using a "singly linked" Linked List!Notice the difference between a "Linked List" and a "Linked Data Structure".
Key Points
- A generic class allows you to have a place holder Class Type (usually T or E) until one is specified in the client class.
- There is a difference between making a class using a "Linked List" or a "Linked Data Structure".
Where to find starter code in my-api
package.class :utils.MyStack
Where to find the test starter code in my-api
package.class :tests.console.MyStackTest
Where to find the JUNIT TEST code in my-api
package.class :tests.junit.MyStackJUnitTest
Task Check List
- ONLY "for" loops should be used within the data structure class. There is anautomatic 30% deduction,if other loops are used.
- The names of identifiers MUST match the names listed in the description below. Deductions otherwise.
- The Node class must be generic and a nested class within MyQueue.
- Complete coding Assignment in your "my-api"GitHub Repository. You will not be graded otherwise and will receive a 0, if not uploaded there.
- Run JUNIT TEST and take a SNAPSHOT of results. Upload PDF of snapshot of yourJUnitTest results to Canvas.
Design Description:Building A Stack Data Structure
Create a generic class for a "Stack" data structure (LIFO) with the following methods:
| Method | Description | Example |
| push(item) | places given element on top of stack. | stack.push("Tom"); |
| pop() | removes the element at the top of the stack and returns it. Throws anEmptyStackException, if stack is empty. | stack.pop(); |
| peek() | returns the element at the top of the stack without removing it from the stack. Throws anEmptyStackException, if stack is empty. | stack.peek(); |
| size() | returns number of elements in stack. | stack.size(); |
| isEmpty() | checks if stack is empty and returns true, if stack has no elements. | stack.isEmpty(); |
string representation: displays the contents of the stack. Create a string representation of the stack from top (last) to bottom (first) reading left to right. Note: Changes will be made to how this content is displayed in a future lab.
public String toString()
MyStack
outer class: Create the generic MyStack class. This is used to control the linked node structures.
data fields:
- first: stores the memory address of the first Node object of type NodeE>.
- last: stores the memory address of the last Node object of type NodeE>.
- size: stores how many elements are linked, i.e., how many Node objects are linked together.
constructor: uses a default constructor to initialize the data fields.
public MyStack()
outer class methods: your methods should follow the input and output requirements in the Java Standard Library.NOTE : All methods must be implemented. Deductions apply otherwise.
Method | Description | Example |
detach
| removes the node at the top of the stack. This is a private helper method. | private void detach()
|
push | places given element on top of stack. | public E push(E item) |
pop | removes the element at the top of the stack and returns it. Throws anEmptyStackException, if stack is empty.
| public E pop() |
peek | returns the element at the top of the stack without removing it from the stack. Throws anEmptyStackException, if stack is empty.
| public E peek() |
size | returns number of elements in stack. | public int size() |
isEmpty | checks if stack is empty and returns true, if stack has no elements. | public boolean isEmpty() |
NOTE : All methods must be implemented. Deductions apply otherwise.
inner class: class inside the body of another class.
The outer class MyStack class includes a nested static generic Node class, i.e. astatic innerclass within the Linked List class.Note: This private class does not require access to instance members of the outer class, so it is declaredstatic. This means that the node object won’t be coupled to the outer class object, and hence will be more optimal ...since it won’t require additional heap/stack memory.
data fields:
- data: hold the data stored in each node as is of typeE.
- next: stores the location of the next node in the list.
constructor:
A constructor that receives parameters for data, next and prev.
public Node(Node next, E data)
Week-02 | Queues
About
Objective:The purpose of this exercise is to create a Queue (FIFO) data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results of using the library features should be identical with your own version (My API). However, the underlying implementation should follow with the descriptions listed below.
Testing your skills.
Now that you have tested your data structure making strategies. You have already been introduced to Queues in Practice It, now you will design and implement your own Queue data structure.
Instructions: Create a generic Queue class using "singly linked" data structure. NOTE: This isNOT THE SAME AS using a "singly linked" Linked List!Notice the difference between a "Linked List" and a "Linked Data Structure" that uses the underlying linked node objects.
Key Points
- A generic class allows you to have a place holder Class Type (usually T or E) until one is specified in the client class.
- There is a difference between making a class using a "Linked List" or a "Linked Data Structure".
Where to find starter code in my-api
package.class :utils.MyQueue
Where to find the test starter code in my-api
package.class :tests.console.MyQueueTest
Where to find the JUNIT TEST code in my-api
package.class :tests.junit.MyQueueJUnitTest
Task Check List
- ONLY "for" loops should be used within the data structure class. There is anautomatic 30% deduction,if other loops are used.
- The names of identifiers MUST match the names listed in the description below. Deductions otherwise.
- The Node class must be generic and a nested class within MyQueue.
- Complete coding Assignment in your "my-api"GitHub Repository. You will not be graded otherwise and will receive a 0, if not uploaded there.
- Run JUNIT TEST and take a SNAPSHOT of results. Upload PDF of snapshot of yourJUnitTest results to Canvas.
Building A Queue Data Structure
Create a generic class for a "Queue" data structure (FIFO) with the following methods:
Method | Description | Example |
add(item) | places given element at back of queue. | queue.add("Tom"); |
remove() | removes element from front of queue and returns it.Throws aNoSuchElementException, if queue is empty.
| queue.remove(); |
peek() | returns front element from queue without removing it from the queue, returnsnull, if queue is empty. | queue.peek(); |
size() | returns number of elements in queue. | queue.size(); |
isEmpty() | returns true, if queue has no elements. | queue.isEmpty(); |
string representation: displays the contents of the queue from left (front) to right (back).
create a string representation of the queue from "front" to "back" reading left to right.
public String toString()
Node Nested Class for MyQueue
The generic MyQueue class includes a static Node class as a nested class, i.e. astatic innerclass within the Linked List class.
inner class: class inside the body of another class.
Note: This private class does not require access to instance members of the outer class, so it is declaredstatic. This means that the node object won’t be coupled to the outer class object, thus will be more optimal since it won’t require additional heap/stack memory.
data fields:
- data: hold the data stored in each node as is of typeE.
- next: stores the location of the next node in the list.
constructor:
A constructor that receives parameters for data, and prev and calls the second constructor.
public Node(E data)
Notice the difference in the additional content for Node from MyStack class.
A constructor that receives parameters for data, next and prev.
public Node(Node next, E data)
MyQueue
outer class: This class is used to control the linked node structures.
data fields:
- first: stores the memory address of the first Node object of type NodeE>.
- last: stores the memory address of the last Node object of type NodeE>.
- size: stores how many elements are linked, i.e., how many Node objects are linked together.
constructor: uses a default constructor to initialize the data fields.
public MyQueue()
outer class methods: your methods should follow the input and output requirements in the Java Standard Library.NOTE : All methods must be implemented. Deductions apply otherwise.
Method | Description | Example |
add | places given element at back of queue and updates the number elements in queue. | public boolean add(E item) |
append
| a helper method to "help" the add method append data at back of queue. DOES NOT update up the number of elements in the queue.
| private void append(E item) |
detach
| removes the node at the front of the queue and returns the deleted element. DOES NOT update up the number of elements in the queue. This is a private helper method. | private E detach()
|
remove | removes element from front of queue and returns it, and reduces size of queue. ThrowsNoSuchElementException, if queue is empty.
| public E remove() |
peek | returns front element from queue without removing it from the queue, returnsnull, if queue is empty. | public E peek() |
size | returns number of elements in queue. | public int size() |
isEmpty | returns true, if queue has no elements. | public boolean isEmpty() |
NOTE : All methods must be implemented. Deductions apply otherwise.
Example:
Read from left to right
add order: "Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"
front[Red, Orange, Yellow, Green, Blue, Indigo, Violet]back
Removal Example:
Read from left to right
front[Red, Orange, Yellow, Green, Blue, Indigo, Violet] back
front[Orange, Yellow, Green, Blue, Indigo, Violet] back
front[Yellow, Green, Blue, Indigo, Violet] back
front[Green, Blue, Indigo, Violet] back