Part 1: Writing JUnit tests for LinkedStack

1. Refer to the testPush(), and testPop() test methods andcomplete the testPeek() method by:

a) creating String-boundinstances of the LinkedStack,*

b) pushing, popping andpeeking as needed, and

c) adding assert statements totest the stack’s state (more details below)

* This is important. You needsomething like this in each method: LinkedStackinstance = new LinkedStack<>();

Method	What to test for
testPush ()	a new stack is empty
	pushing elements onto the stack increases its size
	elements are pushed onto the top of the stack
testPop ()	popping from a stack that has elements decrements its size
	popping returns the element at the top of the stack
	popping mutates the stack by removing the top element
	popping from an empty stack throws an empty collectionexception
	empty collection exceptions are not thrown if the stack is notempty
testPeek ()	peek does not change the state of the stack (in terms of size,content of order)
	peek returns the element at the top of the stack
	peek from an empty stack should throw an exception (put anassert in the catch part of a try-catch)
	peek at non-empty stack shouldn’t throw exception

Here is a code snippet for the popTest() that checks theexception handling:

@Test(expected=EmptyCollectionException.class)public void testPop1() throws Exception {        LinkedStack instance = new LinkedStack<>();       instance.pop();}@Testpublic void testPop2() throws Exception {       LinkedStack instance = new LinkedStack<>();       assertTrue(instance.size() == 0);       String name1 = new String("Ellen");       instance.push(name1);       String name2 = new String("Wei");       instance.push(name2);       assertEquals(instance.size(), 2);       try{             String another = instance.pop();             assertEquals(instance.size(), 1);             assertTrue(name2.equals(another));             instance.pop();             assertTrue(instance.isEmpty());       } catch (Exception ex){             assertFalse(true);       }}

Part 2: Complete the LinkedStackimplementation

Your job is to write code for the push and peek methods. Thepop(), size() and isEmpty() methods are already done.

1. Examine the code for the LinkedStack implementation, inparticular the pop() method.
2. Write a peek() method. This should look like pop, except wearen’t changing the stack at all. Just returning the element.
3. Write a push() method. Remember that the push algorithm willlook like this:

4. Now, run the test class that you worked on in Part 1.Right-click on the test file and select ‘Test File’. View the TestResults window. When you have all the tests for push, pop, and peekpassing, submit it to canvas or show your work to a TA to gettimely feedback.

Part 3: Open ArrayStack.java andLinkedStack.java, compare different implementations, analyze timecomplexity of each method, write down its big O notations, and fillthe comparison table.

Table. StackADT implementations: Arrays versus Singly LinkedLists

Implementation of StackADT

Array

Singly Linked List

Class and Data members

public class ArrayStackimplements StackADT {

T stack[];

int top; //next availableindex

final static int DEFAULT_CAPACITY = 10;

}

public class LinkedStack implements StackADT{

int count;

SingleLinkedNode top;

}

Access

T peek()

O( )

Retrieve element in the index of top-1

O( )

Use the top reference to get to the first node, get the elementfrom it

public T peek(){

}

public T peek(){

}

Push

void push(T element)

O( )

1. if array (stack) is full, expand capacity.

2. Place the given element to the index top of thearray (stack).

3. Increment top.

O( )

1. Create a new linear node holding theelement reference

2. Assign the new node’s next to the same astop

3. Assign top to point to the new node

4. Increment count

public T push(T element){

}

public T push(T element){

}

pop

T pop( )

O( )

1. If stack is empty, throw an EmptyCollectionExceptionexception.

2. Retrieve element temp in the index of top -1.

3. Set stack[top-1] to null.

4. Decrement top

Return temp.

O( )

1. If stack is empty, throw anEmptyCollectionException exception.

2. Declare a temporary node, temp and set itto be the same as top

3. Set the top to its next reference

4. Set the temporary node’s next reference tonull

5. Decrement top

6. Return the data element of them temporarynode

public T pop(T element){

}

public T pop(T element){

}

size()

O( )

Return top

O( )

Return count

public int size(){

}

public int size(){

}

Please write down your answer in sketchbook or a digitaldocument, take a snapshot of the filled table (screenshot orpicture), and your document/PDF to canvas.

Important: Remember to complete theLinkedStack.java and the LinkedStackTest.java files so that bothpartners have a completed implementation file and a completed testfile in coding rooms and that you have hit submit.

Useful Commands -

umm test  // to run tests in LinkedStackTest.javaumm check // to check LinkedStack.java for compiler errors

LinkedStack.java

/*

* To change this license header, choose License Headers inProject Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

package DataStructures;

import ADTs.StackADT;

import Exceptions.EmptyCollectionException;

/*

* @author Qiong

*/

public class LinkedStack implements StackADT{

int count;

SinglyLinkedNode top;

public LinkedStack() {

top = null;

count = 0;

}

public LinkedStack(T data) {

top = new SinglyLinkedNode(data);

count = 1;

}

@Override

public void push(T element) {

// TODO implete the push method

// The push method will insert a node with holds the given inputinto the top of

// the stack

}

@Override

public T pop() throws EmptyCollectionException {

if (this.isEmpty())

throw new EmptyCollectionException();

SinglyLinkedNode node = top;

top = top.getNext();

count--;

node.setNext(null);

return node.getElement();

}

@Override

public T peek() throws EmptyCollectionException {

// TODO: Implement this method

// This should look like pop, except we aren?t changing thestack at all. Just

// returning the element.

return null;

}

@Override

public boolean isEmpty() {

if (count == 0) {

return true;

}

return false;

}

@Override

public int size() {

return count;

}

@Override

public String toString() {

if (top != null) {

return "LinkedListStack{" + "count=" + count + ", top=" +top.getElement() + '}';

} else {

return "LinkedListStack{" + "count=" + count + '}';

}

}

public static void main(String argv[]) {

StackADT cities = newLinkedStack();

try {

cities.push("Tokyo");

cities.push("Atlanta");

cities.pop();

cities.pop();

cities.push("Miami");

cities.pop();

cities.push("Charlotte");

System.out.println("Charlotte".equalsIgnoreCase(cities.peek()));

System.out.println(1 == cities.size());

} catch (Exception ex) {

ex.printStackTrace();

}

}

}

ArrayStack.java

package DataStructures;

import ADTs.StackADT;

import Exceptions.EmptyCollectionException;

import java.util.Arrays;

/**

* @author Qiong

*/

public class ArrayStack implements StackADT{

T stack[];

int top;

final static int DEFAULT_CAPACITY = 10;

public ArrayStack(){

stack = (T [])(new Object[DEFAULT_CAPACITY]);

top = 0;

}

public ArrayStack(int capacity){

stack = (T [])(new Object[capacity]);

top = 0;

}

@Override

public void push(T element) {

if (top == this.stack.length)

expandCapacity();

this.stack[top] = element;

top++;

}

@Override

public T pop() throws EmptyCollectionException {

if (isEmpty()) {

throw new EmptyCollectionException();

}

T element = stack[top-1];

stack[top - 1] = null;

top--;

return element;

}

@Override

public T peek() throws EmptyCollectionException {

if (isEmpty()) {

throw new EmptyCollectionException();

}

return stack[top-1];

}

@Override

public boolean isEmpty() {

return top == 0 ? true : false;

}

@Override

public int size() {

return top;

}

private void expandCapacity() {

this.stack = Arrays.copyOf(this.stack, this.stack.length *2);

}

public static void main(String argv[]){

StackADT cities = newArrayStack();

try{

cities.push("Tokyo");

cities.push("Atlanta");

cities.pop();

cities.pop();

cities.push("Miami");

cities.pop();

cities.push("Charlotte");

System.out.println("Charlotte".equalsIgnoreCase(cities.peek()));

System.out.println(1 == cities.size());

}catch (Exception ex){

ex.printStackTrace();

}

}

}