Lab16 is for an array-based queue implementation, so the task is to implement th
ID: 3806813 • Letter: L
Question
Lab16 is for an array-based queue implementation, so the task is to implement the toString method inside the ArrayQueue class, which means using the array declared there
1. Include a method toString in the interface QueueInterface.
2. Create a method toString in the class ArrayQueue. To test the method toString, call it in the main method of the ArrayQueue class and print the result. You have to create a queue object before that and enqueue some items in the queue, so that the queue is not empty.
ArrayQueue.java
/**
A class that implements the ADT queue by using an expandable
circular array with one unused location.
public final class ArrayQueue<T> implements QueueInterface<T>
{
private T[] queue; // Circular array of queue entries and one unused location
private int frontIndex;
private int backIndex;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public ArrayQueue()
{
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity)
{
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity + 1];
queue = tempQueue;
frontIndex = 0;
backIndex = initialCapacity;
initialized = true;
} // end constructor
public void enqueue(T newEntry)
{
checkInitialization();
ensureCapacity();
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
} // end enqueue
public T getFront()
{
checkInitialization();
if (isEmpty())
throw new EmptyQueueException();
else
return queue[frontIndex];
} // end getFront
public T dequeue()
{
checkInitialization();
if (isEmpty())
throw new EmptyQueueException();
else
{
T front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length;
return front;
} // end if
} // end dequeue
public boolean isEmpty()
{
return frontIndex == ((backIndex + 1) % queue.length);
} // end isEmpty
// Question 3, Chapter 11
public void clear()
{
checkInitialization();
if (!isEmpty())
{ // deallocates only the used portion
for (int index = frontIndex; index != backIndex; index = (index + 1) % queue.length)
{
queue[index] = null;
} // end for
queue[backIndex] = null;
} // end if
frontIndex = 0;
backIndex = queue.length - 1;
} // end clear
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException ("ArrayQueue object is not initialized properly.");
} // end checkInitialization
// Throws an exception if the client requests a capacity that is too large.
private void checkCapacity(int capacity)
{
if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a queue " +
"whose capacity exceeds " +
"allowed maximum.");
} // end checkCapacity
// Doubles the size of the array queue if it is full.
// Precondition: checkInitialization has been called.
private void ensureCapacity()
{
if (frontIndex == ((backIndex + 2) % queue.length)) // If array is full,
{ // double size of array
T[] oldQueue = queue;
int oldSize = oldQueue.length;
int newSize = 2 * oldSize;
checkCapacity(newSize);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[newSize];
queue = tempQueue;
for (int index = 0; index < oldSize - 1; index++)
{
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
} // end for
frontIndex = 0;
backIndex = oldSize - 2;
} // end if
} // end ensureCapacity
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// Add the code for the toString() method here
// public String toString() {
public static void main(String[] args)
{
ArrayQueue<Integer> queue1 = new ArrayQueue<Integer>();
// Add code for initializing the queue
System.out.println(queue1);
} // end main
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
} // end ArrayQueue
EmptyQueueException.java
/**
A class of runtime exceptions thrown by methods to
indicate that a queue is empty.
*/
public class EmptyQueueException extends RuntimeException
{
public EmptyQueueException()
{
this(null);
} // end default constructor
public EmptyQueueException(String message)
{
super(message);
} // end constructor
} // end EmptyQueueException
QueueInterface.java
/**
An interface for the ADT queue.
*/
public interface QueueInterface<T>
{
/* Adds a new entry to the back of this queue.
@param newEntry an object to be added */
public void enqueue(T newEntry);
/* Removes and returns the entry at the front of this queue.
@return either the object at the front of the queue or, if the
queue is empty before the operation, null */
public T dequeue();
/* Retrieves the entry at the front of this queue.
@return either the object at the front of the queue or, if the
queue is empty, null */
public T getFront();
/* Detects whether this queue is empty.
@return true if the queue is empty, or false otherwise */
public boolean isEmpty();
/* Removes all entries from this queue. */
public void clear();
} // end QueueInterface
Explanation / Answer
Please find my implementation.
/**
An interface for the ADT queue.
*/
public interface QueueInterface<T>
{
/* Adds a new entry to the back of this queue.
@param newEntry an object to be added */
public void enqueue(T newEntry);
/* Removes and returns the entry at the front of this queue.
@return either the object at the front of the queue or, if the
queue is empty before the operation, null */
public T dequeue();
/* Retrieves the entry at the front of this queue.
@return either the object at the front of the queue or, if the
queue is empty, null */
public T getFront();
/* Detects whether this queue is empty.
@return true if the queue is empty, or false otherwise */
public boolean isEmpty();
/* Removes all entries from this queue. */
public void clear();
public String toString();
} // end QueueInterface
/**
A class that implements the ADT queue by using an expandable
circular array with one unused location.
**/
public final class ArrayQueue<T> implements QueueInterface<T>
{
private T[] queue; // Circular array of queue entries and one unused location
private int frontIndex;
private int backIndex;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public ArrayQueue()
{
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity)
{
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity + 1];
queue = tempQueue;
frontIndex = 0;
backIndex = initialCapacity;
initialized = true;
} // end constructor
public void enqueue(T newEntry)
{
checkInitialization();
ensureCapacity();
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
} // end enqueue
public T getFront()
{
checkInitialization();
if (isEmpty())
throw new EmptyQueueException();
else
return queue[frontIndex];
} // end getFront
public T dequeue()
{
checkInitialization();
if (isEmpty())
throw new EmptyQueueException();
else
{
T front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length;
return front;
} // end if
} // end dequeue
public boolean isEmpty()
{
return frontIndex == ((backIndex + 1) % queue.length);
} // end isEmpty
// Question 3, Chapter 11
public void clear()
{
checkInitialization();
if (!isEmpty())
{ // deallocates only the used portion
for (int index = frontIndex; index != backIndex; index = (index + 1) % queue.length)
{
queue[index] = null;
} // end for
queue[backIndex] = null;
} // end if
frontIndex = 0;
backIndex = queue.length - 1;
} // end clear
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException ("ArrayQueue object is not initialized properly.");
} // end checkInitialization
// Throws an exception if the client requests a capacity that is too large.
private void checkCapacity(int capacity)
{
if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a queue " +
"whose capacity exceeds " +
"allowed maximum.");
} // end checkCapacity
// Doubles the size of the array queue if it is full.
// Precondition: checkInitialization has been called.
private void ensureCapacity()
{
if (frontIndex == ((backIndex + 2) % queue.length)) // If array is full,
{ // double size of array
T[] oldQueue = queue;
int oldSize = oldQueue.length;
int newSize = 2 * oldSize;
checkCapacity(newSize);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[newSize];
queue = tempQueue;
for (int index = 0; index < oldSize - 1; index++)
{
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
} // end for
frontIndex = 0;
backIndex = oldSize - 2;
} // end if
} // end ensureCapacity
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//Add the code for the toString() method here
public String toString() {
String result = "";
for (int index = 0; index < queue.length - 1; index++)
{
result = result + queue[index]+" ";
} // end for
return result;
}
public static void main(String[] args)
{
ArrayQueue<Integer> queue1 = new ArrayQueue<Integer>();
// Add code for initializing the queue
for(int i=1; i<10; i++)
queue1.enqueue(i);
System.out.println(queue1);
System.out.println(queue1.dequeue());
} // end main
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
} // end ArrayQueue
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.