Java Homework Help The book is Data Sructures and Algorithms. The code for the c
ID: 3871093 • Letter: J
Question
Java Homework Help
The book is Data Sructures and Algorithms.
The code for the classes is from the textbook just need help on the client class.
Stack Interface
/**
*
* @author Robert
* @version
* Stack interface that declares methods for the stacks
*/
public interface Stack<E> {
/**
* Returns the number of elements in the stack
* @return number of elements in the stack.
* */
int size();
/**
* Tests whether the stack is empty.
* @return true if stack is empty, false otherwise
*/
boolean isEmpty();
/**
* Inserts an element at the top of the stack
* @param e the element to be inserted
*/
void push(E e);
/**
* Returns, but doesn't remove, the element at the top of the stack.
* @return top element in the stack (or null if empty)
*/
E top();
/**
* Removes and returns the top element from the stack.
* @return element removed (or null if empty)
*/
E pop();
}
Queue Interface
/**
*
* @author Robert
*/
public interface Queue<E> {
/** Returns the number of elements in the queue.*/
int size();
/** Tests whether the queue is empty.*/
boolean isEmpty();
/** Inserts an element at the rear of the queue.*/
void enqueue(E e);
/** Returns, but doesn't remove, the first element of the queue (null if empty).*/
E first();
/** Removes and returns the first element of the queue (null if empty).*/
E dequeue();
}
ArrayStack Class
/**
*
* @author Robert
*/
public class ArrayStack<E> implements Stack<E> {
public static final int CAPACITY = 1000; //default array capacity
private E[] data; //generic array used for storage
private int t = -1;
public ArrayStack() { this(CAPACITY);} //constructs stack with default capacity
public ArrayStack(int capacity) { //constructs stack with given capacity
data = (E[]) new Object[capacity]; //safe cast; complier may give warning
}
public int size() { return (t + 1);}
public boolean isEmpty() {return(t == -1);}
public void push(E e) throws IllegalStateException {
if (size() == data.length) throw new IllegalStateException("Stack is full");
data[++t] = e; //increment t before storing new item
}
public E top() {
if(isEmpty()) return null;
return data[t];
}
public E pop() {
if(isEmpty()) return null;
E answer = data[t];
data[t] = null; //deference to help garbage collection
t--;
return answer;
}
}
LinkedStack Class
/**
*
* @author Robert
*/
public class LinkedStack<E> implements Stack<E> {
private SinglyLinkedList<E> list = new SinglyLinkedList<>(); //an empty list
public LinkedStack() {} //new stack relies on intially empty list
public int size() { return list.size(); }
public boolean isEmpty() { return list.isEmpty();}
public void push(E element) { list.addFirst(element); }
public E top() { return list.first(); }
public E pop() { return list.removeFirst(); }
}
ArrayQueue Class
/**
*
* @author Robert
*/
/** Implementation of the queue ADT using a fixed-length array.*/
public class ArrayQueue<E> implements Queue<E> {
//instance variables
private static final int CAPACITY = 1000;
private E[] data; //generic array used for storage.
private int f = 0; //index of the front element
private int sz = 0; // current number of elements
//constructors
public ArrayQueue() {this(CAPACITY);} //constructs queue with default capacity
public ArrayQueue(int capacity) { //constructs queue with given capacity
data = (E[]) new Object[capacity];//safe cast; compiler may give warning
}
//methods
/** Returns the number of elements in the queue.*/
public int size() { return sz; }
/** Tests whether the queue is empty.*/
public boolean isEmpty() { return (sz == 0); }
/** Inserts an element at the rear of the queue.*/
public void enqueue(E e) throws IllegalStateException {
if (sz == data.length) throw new IllegalStateException("Queue is full");
int avail = (f + sz) % data.length; //modular arithmetic
data[avail] = e;
sz++;
}
/** Returns, but doesn't remove, the first element of the queue (null if empty).*/
public E first() {
if(isEmpty()) return null;
return data[f];
}
/** Removes and returns the first element of the queue (null if empty).*/
public E dequeue() {
if(isEmpty()) return null;
E answer = data[f];
data[f] = null;
f = (f + 1) % data.length;
sz--;
return answer;
}
}
LinkedQueue Class
/**
*
* @author Robert
*/
public class LinkedQueue<E> implements Queue<E> {
private SinglyLinkedList<E> list = new SinglyLinkedList<>(); //empty list
public LinkedQueue() {}
public int size() {return list.size();}
public boolean isEmpty() { return list.isEmpty(); }
public void enqueue(E element) {list.addLast(element);}
public E first() { return list.first(); }
public E dequeue() { return list.removeFirst(); }
}
The Main Client Class requires the following:
In your client class you are going to compare the run times of the static (array based) classes to the dynamic (linked based) classes.
The basic test will be to:
Start a timer
Fill a queue with N elements
Dequeue all of the elements from the queue onto a stack
Pop all of the elements from the stack back into the queue
Note that this reverses the order of the queue
Stop the timer.
You will perform two tests. One with array based stacks and queues and one with linked based stacks and queues.
Use random Integers as the element and start with N = one million.
Increase N by a factor or 10 until you would run out of memory or until the run time becomes excessive (more than 10 minutes). There may be other types of exceptions that you will need to deal with. In any case your program should exit gracefully and not crash. You cannot code a hard upper limit for N or time into your Client. You program needs to predict when it will fail and not run that test.
You client should be loop driven so that N is automatically increment on each pass.
You output should look something like (make sure that you line up as a nicely formatted table (hint, use printf, and in your Word Document use Courier New font):
N Array Linked
1,000,000 7 14
10,000,000 700 140
100,000,000 7,000 1,400
1,000,000,000 Out of Memory 14,000
10,000,000,000 Out of Memory Out of Time
Explanation / Answer
First create the Test client class
public class TestClient
{
public static void main(String[] args)
{
System.out.println(" N Array Linked");
Random rand = new Random(); // creates the object of Random class to generate random numbers
while(true)
{
long n=100000L;
long astartTime = System.currentTimeMillis(); // fetchs the current time from system in miliseconds
long aelapsedTime = 0L.
System.out.print(" "+n);
try
{
ArrayQueue<E> aqueue=new ArrayQueue<E>(n);
ArrayStack<E> astack=new ArrayStack<E>(n);
// fill the queue
for(long i=0L;i<n;i++)
{
int ri = rand.nextInt(50) + 1; // generates the random integer in the range of 1 to 50. You can choose your range
aqueue.enqueue(ri);
}
//dequeue elements and push into stack
for(long i=0L;i<n;i++)
{
long p=aqueue.dequeue();
astack.push(p);
}
//pop all elements and queue back to the queue
for(long i=0L;i<n;i++)
{
long p=astack.pop();
aqueue.enqueue(p);
}
aelapsedTime = (new Date()).getTime() - astartTime;
System.out.print(" "+(aelapsedTime/60000L));
}
catch(OutOfMemoryError e) // handles the out of memory exception
{
System.out.print(" Out of Memory");
}
LinkedQueue<E> lqueue=new LinkedQueue<E>();
LinkedStack<E> lstack=new LinkedStack<E>();
for(long i=0L;i<n;i++)
{
int ri = rand.nextInt(50) + 1; // generates the random integer in the range of 1 to 50. You can choose your range
lqueue.enqueue(ri);
}
//dequeue elements and push into stack
for(long i=0L;i<n;i++)
{
long p=lqueue.dequeue();
lstack.push(p);
}
//pop all elements and queue back to the queue
for(long i=0L;i<n;i++)
{
long p=lstack.pop();
lqueue.enqueue(p);
}
long lelapsedTime = (new Date()).getTime() - aelapsedTime;
if(lelapsedTime >= 10)
{
System.out.print(" Out of time ");
break; // breaks the while loop
}
else
{
System.out.print(" "+(lelapsedTime/60000L));//converts miliseconds to minutes
}
n=n*10L; // multiplies the range by 10
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.