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 in your "labs" project. However, the underlying implementation should follow with the descriptions listed below.

Instructions : Create a Stack class using "singly linked" nodes. This means that the Stack itself is implement as a Singly Linked Data Structure. NOTE: This does NOT mean use the implementation of the Singly Linked List! There is a difference between creating a "Linked List" and a "Linked Data Structure".

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.

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 "labs"

package.class : utils.MyStack

Where to find the test starter code in "labs"

package.class : lab$03$$stacksqueues.Test$01$MyStack

Where to find the JUNIT TEST code in "labs"

package.class : junits.MyStackJUnitTest

Task Check List

Create a Generic MyStack class and fill in the body with the features $($methods$,$ data fields etc.$)$ described below.

ONLY "for" loops should be used within the data structure class. There is an automatic $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 MyStack.

Complete coding Assignment in your "labs$-$Lastname$-$Firstname" 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 a PDF of a snapshot of your JUnitTest results and output etc. to this assignment in Canvas.

Commit to GitHub weekly your progress, with a descriptive message of what was done e$.$g "added remove method 'Data Structure Name' $[$Date$]"$ or if completed $>$ "COMPLETE 'Data Structure Name' passed all JUNIT tests"

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 an EmptyStackException, if stack is empty. stack.pop$()$;

peek$()$ returns the element at the top of the stack without removing it from the stack. Throws an EmptyStackException, 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 Node.

last : stores the memory address of the last Node object of type Node.

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 and returns removed item. This is a private helper method.

private E 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 an EmptyStackException, if stack is empty.

public E pop$()$

peek

returns the element at the top of the stack without removing it from the stack. Throws an EmptyStackException, 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.

Node $($Underlying Linked Data Structure$)$

inner class: class inside the body of another class.

The outer class MyStack class includes a nested static generic Node class, i$.$e$.$ a static inner class within the Linked List class. Note: This private class does not require access to ins