Question
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
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;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started