Question
Problem Create a generic class LinkedStack to represent a stack capable of storing any type of object. Specification Stack.zip contains the source code files you
Problem
Create a generic class LinkedStack to represent a stack capable of storing any type of object.
Specification
Stack.zip contains the source code files you need for this project.
Stack.java - Stack interface
SinglyLinkedList.java and SLNode.java - linked list and node classes
Create a LinkedStack class that implements the Stack interface and uses SinglyLinkedList methods to implement the Stack methods.
Validate the class using the "test-driven" development model. Use the following document to guide the development of a test case for each LinkedStack method using JUnit (M1-A2: JUnit Lab) as the test environment.Stack Behavior.pdf
Settings
Create a test program to demonstrate a Stack of Integers and a stack of Persons.
package Stack;
/**
* 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();
}
/*
* CSIS1410
* generic class SinglyLinkedList
*/
package LinkedList;
import Person.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));
}
}
package LinkedList;
/**
* 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
/**
* 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
{
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
{
return this.successor;
}
/**
* Set the successor to this node in the list.
* @param newSuccessor this node's new successor
*/
public void setSuccessor( SLNode
{
this.successor = newSuccessor;
}
}
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
