This lab will give you a concrete idea of why we made some of the decisions we d
ID: 3759878 • Letter: T
Question
This lab will give you a concrete idea of why we made some of the decisions we did in the linked list and array implementations of a stack.
1. (10 pts) Write a NaughtyLLStack<E> class. Like the LLStack<E> class that we wrote in lecture, your class should implement a stack using a linked list. However, it should perform the push and pop operations from the tail of the list instead of the head. Furthermore, do not maintain a reference to the list’s tail node.
2. (10 pts) Write a NaughtyArrayStack<E> class. Like the ArrayStack<E> class that we wrote in lecture, your class should implement a stack using an array. However, it should fix the top of the stack at index 0 of the array, meaning that when push or pop operations are performed, all array elements need to be shifted up or down by 1 index.
3. (5 pts) Write a client program that performs a large number* of push and pop operations on the “good” and “bad” implementations, and displays the time required to do so.
Remember that you can use the built-in method System.currentTimeMillis() to get the current system time in milliseconds. Use this as a “stopwatch” – call currentTimeMillis once to get the starting time, execute the code you want to time, and then call currentTimeMillis again to get the ending time. The elapsed time is simply the difference between the start and end times.
THESE ARE THE IN CLASS CODES USING JAVA
import java.util.EmptyStackException;
public class LLStack<E> implements Stack<E>
{
private static class LLNode<E>
{
private E data; // data stored in this node
private LLNode<E> next; // a reference to the next node in the list
public LLNode(E data, LLNode<E> next)
{
this.data = data;
this.next = next;
}
}
private LLNode<E> head = null;
public boolean isEmpty()
{
return (head == null);
}
// Same as adding to the head of the list
public void push(E newData)
{
head = new LLNode<E>(newData, head);
}
// Same as removing from the head of the list
public E pop()
{
if (!isEmpty()) {
E toReturn = head.data;
head = head.next;
return toReturn;
} else {
throw new EmptyStackException();
}
}
public E peek()
{
if (!isEmpty()) {
return head.data;
} else {
throw new EmptyStackException();
}
}
public String toString()
{
String s = "LLStack with elements (top to bottom): ";
for (LLNode<E> temp = head; temp != null; temp = temp.next) {
s += temp.data + " ";
}
return s;
}
public static void main(String[] args)
{
Stack<Pancake> breakfast = new LLStack<Pancake>();
for (int i = 10; i <= 300; i += 10) {
breakfast.push(new Pancake(i));
}
System.out.println(breakfast);
System.out.println(breakfast.peek());
System.out.println(breakfast);
for (int i = 0; i < 40; i++)
System.out.println(breakfast.pop());
}
}
THE ARRAY CLASS
/**
* Implements a stack using an array as the underlying data structure. The
* high index of the array corresponds to the top of the stack, in order to
* avoid having to shift array elements up and down with push and pop operations.
*
* @author (your name)
* @version (a version number or a date)
*/
import java.util.EmptyStackException;
public class ArrayStack<E> implements Stack<E>
{
private E[] data = (E[])(new Object[10]);
private int size;
public boolean isEmpty()
{
return (size == 0);
}
// Same as adding new data in an array list
public void push(E newData)
{
if (size == data.length) {
E[] newDataArray = (E[])(new Object[size*2]);
for (int i = 0; i < size; i++)
newDataArray[i] = data[i];
data = newDataArray;
}
data[size] = newData;
size++;
}
public E pop()
{
if (!isEmpty()) {
E temp = data[size-1];
data[size-1] = null;
size--;
return temp;
} else {
throw new EmptyStackException();
}
}
public E peek()
{
if (!isEmpty()) {
return data[size-1];
} else {
throw new EmptyStackException();
}
}
public String toString()
{
String s = "ArrayStack with elements (top to bottom): ";
for (int i = size - 1; i >= 0; i--) {
s += data[i] + " ";
}
return s;
}
public static void main(String[] args)
{
Stack<Pancake> breakfast = new ArrayStack<Pancake>();
for (int i = 10; i <= 300; i += 10) {
breakfast.push(new Pancake(i));
}
System.out.println(breakfast);
System.out.println(breakfast.peek());
System.out.println(breakfast);
for (int i = 0; i < 40; i++)
System.out.println(breakfast.pop());
}
}
Explanation / Answer
import java.util.EmptyStackException;
public class LLStack<E> implements Stack<E>
{
private static class LLNode<E>
{
private E data; // data stored in this node
private LLNode<E> next; // a reference to the next node in the list
public LLNode(E data, LLNode<E> next)
{
this.data = data;
this.next = next;
}
}
private LLNode<E> head = null;
public boolean isEmpty()
{
return (head == null);
}
// Same as adding to the head of the list
public void push(E newData)
{
head = new LLNode<E>(newData, head);
}
// Same as removing from the head of the list
public E pop()
{
if (!isEmpty()) {
E toReturn = head.data;
head = head.next;
return toReturn;
} else {
throw new EmptyStackException();
}
}
public E peek()
{
if (!isEmpty()) {
return head.data;
} else {
throw new EmptyStackException();
}
}
public String toString()
{
String s = "LLStack with elements (top to bottom): ";
for (LLNode<E> temp = head; temp != null; temp = temp.next) {
s += temp.data + " ";
}
return s;
}
public static void main(String[] args)
{
Stack<Pancake> breakfast = new LLStack<Pancake>();
for (int i = 10; i <= 300; i += 10) {
breakfast.push(new Pancake(i));
}
System.out.println(breakfast);
System.out.println(breakfast.peek());
System.out.println(breakfast);
for (int i = 0; i < 40; i++)
System.out.println(breakfast.pop());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.