1. Can you "pop" from a queue -- in other words, is there any reason why you couldn't just copy over the method (after modifying it for generics) to use it in the queue class? 2. Look at the pre-condition and post-condition for nextInt (reproduced below): private int nextIndex(int i) // Precondition: 0 <= i and i < data.length // Postcondition: If i+1 is data.length, // then the return value is zero; otherwise // the return value is i+1. Explain them, including answers to the following in your response : What method uses nextIndex( )? Why is the precondition necessary? Why does the behavior described postcondition make sense? import java.util.EmptyStackException; public class ArrayStack implements Cloneable { private int[ ] data; private int manyItems; public ArrayStack( ) { final int INITIAL_CAPACITY = 10; manyItems = 0; data = (int[]) new int[INITIAL_CAPACITY]; } public ArrayStack(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException ("initialCapacity too small " + initialCapacity); manyItems = 0; data = (int[]) new int[initialCapacity]; } public ArrayStack clone( ) { // Clone an ArrayStack. ArrayStack answer; try { answer = (ArrayStack) super.clone( ); } catch (CloneNotSupportedException e) { throw new RuntimeException ("This class does not implement Cloneable"); } answer.data = data.clone( ); return answer; } public void ensureCapacity(int minimumCapacity) { int biggerArray[ ]; if (data.length < minimumCapacity) { biggerArray = (int[]) new int[minimumCapacity]; System.arraycopy(data, 0, biggerArray, 0, manyItems); data = biggerArray; } } public int getCapacity( ) { return data.length; } public boolean isEmpty( ) { return (manyItems == 0); } public int peek( ) { if (manyItems == 0) // EmptyStackException is from java.util and its constructor has no argument. throw new EmptyStackException( ); return data[manyItems-1]; } public int pop( ) { if (manyItems == 0) throw new EmptyStackException( ); return data[--manyItems]; } public void push(int item) { if (manyItems == data.length) { } data[manyItems] = item; manyItems++; } public int size( ) { return manyItems; } public void trimToSize( ) { int trimmedArray[ ]; if (data.length != manyItems) { trimmedArray = (int[]) new int[manyItems]; System.arraycopy(data, 0, trimmedArray, 0, manyItems); data = trimmedArray; } } } import java.util.NoSuchElementException; public class ArrayQueue implements Cloneable { private E[ ] data; private int manyItems; private int front; private int rear; public ArrayQueue( ) { final int INITIAL_CAPACITY = 10; manyItems = 0; data = (E[]) new Object[INITIAL_CAPACITY]; } public ArrayQueue(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException ("initialCapacity is negative: " + initialCapacity); manyItems = 0; data = (E[]) new Object[initialCapacity]; } public ArrayQueue clone( ) { ArrayQueue answer; try { answer = (ArrayQueue) super.clone( ); } catch (CloneNotSupportedException e) { throw new RuntimeException ("This class does not implement Cloneable"); } answer.data = data.clone( ); return answer; } public void add(E item) { if (manyItems == data.length) { ensureCapacity(manyItems*2 + 1); } if (manyItems == 0) { front = 0; rear = 0; } else rear = nextIndex(rear); data[rear] = item; manyItems++; } public void ensureCapacity(int minimumCapacity) { E[ ] biggerArray; int n1, n2; if (data.length >= minimumCapacity) return; else if (manyItems == 0) data = (E[]) new Object[minimumCapacity]; else if (front <= rear) { biggerArray = (E[]) new Object[minimumCapacity]; System.arraycopy(data, front, biggerArray, front, manyItems); data = biggerArray; } else { biggerArray = (E[]) new Object[minimumCapacity]; n1 = data.length - front; n2 = rear + 1; System.arraycopy(data, front, biggerArray, 0, n1); System.arraycopy(data, 0, biggerArray, n1, n2); front = 0; rear = manyItems-1; data = biggerArray; } } public int getCapacity( ) { return data.length; } public boolean isEmpty( ) { return (manyItems == 0); } private int nextIndex(int i) { if (++i == data.length) return 0; else return i; } public E remove( ) { E answer; if (manyItems == 0) throw new NoSuchElementException("Queue underflow"); answer = data[front]; front = nextIndex(front); manyItems--; return answer; } public int size( ) { return manyItems; } public void trimToSize( ) { E[] trimmedArray; int n1, n2; if (data.length == manyItems) return; else if (manyItems == 0) data = (E[]) new Object[0]; else if (front <= rear) { trimmedArray = (E[]) new Object[manyItems]; System.arraycopy(data, front, trimmedArray, front, manyItems); data = trimmedArray; } else { trimmedArray = (E[]) new Object[manyItems]; n1 = data.length - front; n2 = rear + 1; System.arraycopy(data, front, trimmedArray, 0, n1); System.arraycopy(data, 0, trimmedArray, n1, n2); front = 0; rear = manyItems-1; data = trimmedArray; } }
1. Can you "pop" from a queue -- in other words, is there any reason why you couldn't just copy over the method (after modifying it for generics) to use it in the queue class?
2. Look at the pre-condition and post-condition for nextInt (reproduced below):
private int nextIndex(int i)
// Precondition: 0 <= i and i < data.length
// Postcondition: If i+1 is data.length,
// then the return value is zero; otherwise
// the return value is i+1.
Explain them, including answers to the following in your response :
- What method uses nextIndex( )?
- Why is the precondition necessary?
- Why does the behavior described postcondition make sense?
import java.util.EmptyStackException;
public class ArrayStack implements Cloneable
{
private int[ ] data;
private int manyItems;
public ArrayStack( )
{
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = (int[]) new int[INITIAL_CAPACITY];
}
public ArrayStack(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("initialCapacity too small " + initialCapacity);
manyItems = 0;
data = (int[]) new int[initialCapacity];
}
public ArrayStack clone( )
{ // Clone an ArrayStack.
ArrayStack answer;
try
{
answer = (ArrayStack) super.clone( );
}
catch (CloneNotSupportedException e)
{
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.data = data.clone( );
return answer;
}
public void ensureCapacity(int minimumCapacity)
{
int biggerArray[ ];
if (data.length < minimumCapacity)
{
biggerArray = (int[]) new int[minimumCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
}
public int getCapacity( )
{
return data.length;
}
public boolean isEmpty( )
{
return (manyItems == 0);
}
public int peek( )
{
if (manyItems == 0)
// EmptyStackException is from java.util and its constructor has no argument.
throw new EmptyStackException( );
return data[manyItems-1];
}
public int pop( )
{
if (manyItems == 0)
throw new EmptyStackException( );
return data[--manyItems];
}
public void push(int item)
{
if (manyItems == data.length)
{
}
data[manyItems] = item;
manyItems++;
}
public int size( )
{
return manyItems;
}
public void trimToSize( )
{
int trimmedArray[ ];
if (data.length != manyItems)
{
trimmedArray = (int[]) new int[manyItems];
System.arraycopy(data, 0, trimmedArray, 0, manyItems);
data = trimmedArray;
}
}
}
import java.util.NoSuchElementException;
public class ArrayQueue<E> implements Cloneable
{
private E[ ] data;
private int manyItems;
private int front;
private int rear;
public ArrayQueue( )
{
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = (E[]) new Object[INITIAL_CAPACITY];
}
public ArrayQueue(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("initialCapacity is negative: " + initialCapacity);
manyItems = 0;
data = (E[]) new Object[initialCapacity];
}
public ArrayQueue<E> clone( )
{
ArrayQueue<E> answer;
try
{
answer = (ArrayQueue<E>) super.clone( );
}
catch (CloneNotSupportedException e)
{
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.data = data.clone( );
return answer;
}
public void add(E item)
{
if (manyItems == data.length)
{
ensureCapacity(manyItems*2 + 1);
}
if (manyItems == 0)
{
front = 0;
rear = 0;
}
else
rear = nextIndex(rear);
data[rear] = item;
manyItems++;
}
public void ensureCapacity(int minimumCapacity)
{
E[ ] biggerArray;
int n1, n2;
if (data.length >= minimumCapacity)
return;
else if (manyItems == 0)
data = (E[]) new Object[minimumCapacity];
else if (front <= rear)
{
biggerArray = (E[]) new Object[minimumCapacity];
System.arraycopy(data, front, biggerArray, front, manyItems);
data = biggerArray;
}
else
{
biggerArray = (E[]) new Object[minimumCapacity];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, biggerArray, 0, n1);
System.arraycopy(data, 0, biggerArray, n1, n2);
front = 0;
rear = manyItems-1;
data = biggerArray;
}
}
public int getCapacity( )
{
return data.length;
}
public boolean isEmpty( )
{
return (manyItems == 0);
}
private int nextIndex(int i)
{
if (++i == data.length)
return 0;
else
return i;
}
public E remove( )
{
E answer;
if (manyItems == 0)
throw new NoSuchElementException("Queue underflow");
answer = data[front];
front = nextIndex(front);
manyItems--;
return answer;
}
public int size( )
{
return manyItems;
}
public void trimToSize( )
{
E[] trimmedArray;
int n1, n2;
if (data.length == manyItems)
return;
else if (manyItems == 0)
data = (E[]) new Object[0];
else if (front <= rear)
{
trimmedArray = (E[]) new Object[manyItems];
System.arraycopy(data, front, trimmedArray, front, manyItems);
data = trimmedArray;
}
else
{
trimmedArray = (E[]) new Object[manyItems];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, trimmedArray, 0, n1);
System.arraycopy(data, 0, trimmedArray, n1, n2);
front = 0;
rear = manyItems-1;
data = trimmedArray;
}
}
}
Step by step
Solved in 2 steps
