? Create a class LinkedListStackWithHeadNode that implements the interface Stack
ID: 3582970 • Letter: #
Question
? Create a class LinkedListStackWithHeadNode that implements the interface Stack efficiently
using a linked list. Again, to make it interesting, use an empty header node, as shown below:
Finally, create a subclass SortableArrayListWithIterativeMergeSort<T extends Comparable<T>>
of the class SortedArrayList<T> that implements the method sortSubArray using the Merge Sort
algorithm. However, instead of using recursion, it should use a stack and a while loop with a
switch statement to simulate the recursion, as we discussed in class.
To give you a template to work from, I am providing an iterative implementation of the class
FactorialCalculator as well as the original recursive implementation. Note, however, that the
recursive version of calculateFactorial has a single recursive call, so that the activation record
has a single return point within the method. Merge Sort, on the other hand, has two recursive
calls, and so has two return points within the method. Thus, in addition to quite different
activation records, the switch statement may have more return points.
Explanation / Answer
import java.lang.Iterable;
import java.util.*;
public class ArrayStack <Item> implements Stack <Item>
{
private Item container[];
private int top;
private final static int DEFAULT_SIZE = 10;
public ArrayStack ()
{
this(DEFAULT_SIZE);
}
public ArrayStack (int initSize)
{
container = (Item[]) new Object [initSize];
top = -1;
}
public Item getTop()
{
if (top == -1)
return null;
return container[top];
}
public boolean isEmpty()
{
return (top == -1);
}
public Item pop()
{
if (top == -1)
return null;
Item itm = container[top];
container[top--] = null;
if(top > 0 && top == container.length / 4)
resize (container.length/2);
return itm;
}
public void push(Item itm)
{
if (top == container.length - 1)
resize(2 * container.length);
container[++top] = itm;
}
public int size()
{
return (top + 1);
}
private void resize (int newSize)
{
Item t[] = (Item[]) new Object[newSize];
for (int i = 0; i <= top; i++)
t[i] = container[i];
container = t;
}
public Iterator<Item> iterator()
{
return new ArrayStackIterator();
}
private class ArrayStackIterator implements Iterator <Item>
{
private int i = top;
public boolean hasNext()
{
return (i > -1);
}
public Item next()
{
return container[i--];
}
public void remove()
{
// not needed
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.