Create a LinkedStack class that implements the Stack interface and uses a SinglyLinkedList object as the backing store. Validate the class using the "test-driven" development model. Create a test program to demonstrate a Stack of Integers and a stack of Persons. Use the Stack interface provided NOT the Java API Stack. Use the SingleLinkedList class provided NOT the java API LinkedList.

Criteria: Uses linked list as data store and the following methods: isEmpty(), peek(), pop(), push(), size().

package LinkedList;

import LinkedList.Person;

/**

* A simple singly-linked list introduced in the chapter on Fundamental Data

* Structures.

*/

public class SinglyLinkedList

{

private int length; // # elements in the linked list

private SLNode head; // access point to the linked list

private SLNode tail;

/**

* Create an empty SinglyLinkedList.

*/

public SinglyLinkedList()

{

this.length = 0;

this.tail = new SLNode(); // the tail dummy node

this.head = new SLNode(null, this.tail); // the head dummy node

}

/**

* Return a reference to the head of the list.

*

* @return a reference to the head node

*/

public SLNode getHead()

{

return this.head;

}

/**

* Sets the head node to a new list.

*

* @param newHead

* the head node of some list

*/

public void setHead(SLNode newHead)

{

this.head = newHead;

}

/**

* Return the length of this singly linked list.

*

* @return the number of elements in this singly linked list

*/

public int getLength()

{

return this.length;

}

/**

* Add a new element at the beginning of the linked list.

*

* @param e

* the element to add

*/

public void add(E e)

{

SLNode newnode = new SLNode(e, null);

newnode.setSuccessor(this.head.getSuccessor());

this.head.setSuccessor(newnode);

this.length++;

}

/**

* Add element e at position p in this singly linked

* list.

*

* @param e

* the element to add

* @param p

* position to insert e; must be in the range 0 to

* this.size().

* @throws IndexOutOfBoundsException

* if p is outside the range 0 to

* this.length().

*/

public void add(E e, int p)

{

// verify that index p is valid

if ((p < 0) || (p > this.length))

{

throw new IndexOutOfBoundsException("index " + p

+ " is out of range: 0 to " + this.length);

}

SLNode newnode = new SLNode(e, null);

SLNode cursor = this.head;

for (int i = 0; i < p; i++)

{

cursor = cursor.getSuccessor();

}

addAfter(cursor, newnode);

this.length++;

}

/**

* Remove the node at position p and return its element field.

*

* @param p

* the position whose element we are to return

* @return the element in position p

* @throws IndexOutOfBoundsException

* if p is outside the range 0 to length() - 1

*/

public E remove(int p)

{

if ((p < 0) || (p >= this.length))

{

throw new IndexOutOfBoundsException("index " + p

+ " is out of range: 0 to " + (this.length - 1));

}

SLNode cursor = head; // good for p == 0

if (p > 0)

{

cursor = find(p - 1); // get target's predecessor

}

SLNode target = cursor.getSuccessor(); // get the node to remove

// link target to cursor's successor

cursor.setSuccessor(target.getSuccessor());

target.setSuccessor(null);

this.length--;

return target.getElement();

}

/**

* Return the element stored in the node at position p.

*

* @param p

* the position whose element we want

* @return the element from position p of this linked list

* @throws IndexOutOfBoundsException

* if the index p is outside the range 0 to length - 1.

*/

public E getElementAt(int p)

{

SLNode node = this.find(p);

return node.getElement();

}

// PRIVATE UTILITY METHODS

/*

* addAfter - add newnode after node p PRECONDITIONS NOT CHECKED! pre: p and

* newnode are not null post: newnode is inserted after p

*/

private void addAfter(SLNode p, SLNode newnode)

{

newnode.setSuccessor(p.getSuccessor());

p.setSuccessor(newnode);

}

/**

* find - find the first node containing target, return null if target is not

* found

*/

private SLNode find(E target)

{

SLNode cursor = head.getSuccessor();

while (cursor != tail)

{

if (cursor.getElement().equals(target))

{

return cursor; // success

}

else

{

cursor = cursor.getSuccessor();

}

}

return null; // failure

}

/*

* find - find the node at position p throw an exception if the index p is

* outside the range 0 to this.length - 1

*/

private SLNode find(int p)

{

if ((p < 0) || (p >= this.length))

{

throw new IndexOutOfBoundsException();

}

SLNode cursor = head.getSuccessor();

int i = 0;

while (i != p)

{

cursor = cursor.getSuccessor();

i++;

}

return cursor;

}

public static void main(String[] args)

{

System.out.println("--[ Linked List Demo ]--");

SinglyLinkedList myFriends = new SinglyLinkedList();

myFriends.add(new Person("Jack", 4));

System.out.printf("I have %d friend(s) ",myFriends.getLength());

myFriends.add(new Person("Jill", 5));

myFriends.add(new Person("Jane", 5));

myFriends.add(new Person("John", 4));

System.out.printf("I have %d friend(s) ",myFriends.getLength());

System.out.println("My Friends: ");

for(int i=0; i

System.out.println(myFriends.getElementAt(i));

}

}

/** * The structure of a node in the simple singly-linked list * introduced in the chapter on Fundamental Data Structures. */ public class SLNode { private E element; // the data field private SLNode successor; // the link to this node's successor

/** * Create an empty SLNode object. */ public SLNode() { this.element = null; this.successor = null; }

/** * Create an SLNode that stores * theElement and whose successor is * theSuccessor. * @param theElement the element to store in this node * @param theSuccessor this node's successor */ public SLNode( E theElement, SLNode theSuccessor ) { this.element = theElement; this.successor = theSuccessor; }

/** * Return the element stored in this SLNode * object. * @return the element stored in this node */ public E getElement() { return this.element; }

/** * Set the element field for this node. * @param newElement the new element to be stored in * this node */ public void setElement( E newElement ) { this.element = newElement; }

/** * Return this node's successor. * @return this node's successor */ public SLNode getSuccessor() { return this.successor; }

/** * Set the successor to this node in the list. * @param newSuccessor this node's new successor */ public void setSuccessor( SLNode newSuccessor ) { this.successor = newSuccessor; } }

package LinkedList;

/**

* A stack provides last-in-first-out behavior. All access operations on a stack

* are done at its top.

*/

public interface Stack

{

/**

* Determine if the stack is empty.

*

* @return true if the stack is empty, otherwise return false

*/

public boolean isEmpty();

/**

* Return the top element of the stack without removing it. This operation

* does not modify the stack.

*

* @return topmost element of the stack

* @throws EmptyStackException

* if the stack is empty

*/

public E peek();

/**

* Pop the top element from the stack and return it.

*

* @return topmost element of the stack

* @throws EmptyStackException

* if the stack is empty

*/

public E pop();

/**

* Push element on top of the stack.

*

* @param element

* the element to be pushed on the stack.

*/

public void push(E element);

/**

* Return the number of elements currently stored in the stack.

*

* @return topmost element of the stack

*/

public int size();

}

public class Person

{

private String name;

private int age;

/**

* @return the name

*/

public String getName()

{

return name;

}

/**

* @see java.lang.Object#hashCode()

*/

@Override

public int hashCode()

{

final int prime = 31;

int result = 1;

result = prime * result + age;

result = prime * result + ((name == null) ? 0 : name.hashCode());

return result;

}

/* (non-Javadoc)

* @see java.lang.Object#equals(java.lang.Object)

*/

@Override

public boolean equals(Object obj)

{

if (this == obj)

return true;

if (obj == null)

return false;

if (!(obj instanceof Person))

return false;

Person other = (Person) obj;

if (age != other.age)

return false;

if (name == null)

{

if (other.name != null)

return false;

} else if (!name.equals(other.name))

return false;

return true;

}

/* (non-Javadoc)

* @see java.lang.Object#toString()

*/

@Override

public String toString()

{

return String.format("Person [name=%s, age=%s]", name, age);

}

/**

* @param name the name to set

*/

public void setName(String name)

{

this.name = name;

}

/**

* @return the age

*/

public int getAge()

{

return age;

}

/**

* @param age the age to set

*/

public void setAge(int age)

{

this.age = age;

}

/**

* @param name

* @param age

*/

public Person(String name, int age)

{

this.name = name;

this.age = age;

}

}