/** * A class that implements the ADT queue by using an expandable circular arra
ID: 3714819 • Letter: #
Question
/**
* A class that implements the ADT queue by using an expandable circular array
* with one unused location.
*
*/
public 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 static final int DEFAULT_INITIAL_CAPACITY = 50;
public ArrayQueue() {
this(DEFAULT_INITIAL_CAPACITY);
}
public ArrayQueue(int initialCapacity) {
queue = (T[]) new Object[initialCapacity + 1];
frontIndex = 0;
backIndex = initialCapacity;
}
public void enqueue(T newEntry) {
if (isArrayFull())
doubleArray();
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
}
public T getFront() {
T front = null;
if (!isEmpty())
front = queue[frontIndex];
return front;
}
public T dequeue() {
T front = null;
if (!isEmpty()) {
front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length;
}
return front;
}
public boolean isEmpty() {
return frontIndex == ((backIndex + 1) % queue.length);
}
public void clear() {
if (!isEmpty()) { // deallocates only the used portion
for (int index = frontIndex; index != backIndex; index = (index + 1)
% queue.length) {
queue[index] = null;
}
queue[backIndex] = null;
}
frontIndex = 0;
backIndex = queue.length - 1;
}
private boolean isArrayFull() {
return frontIndex == ((backIndex + 2) % queue.length);
}
private void doubleArray() {
T[] oldQueue = queue;
int oldSize = oldQueue.length;
queue = (T[]) new Object[2 * oldSize];
for (int index = 0; index < oldSize - 1; index++) {
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
}
frontIndex = 0;
backIndex = oldSize - 2;
}
public void display() {
for(int i=frontIndex; i!=(backIndex+1)%queue.length; i=(i+1)%queue.length) {
T data = queue[i];
System.out.print(data + " ");
}
System.out.println();
}
public void splice(ArrayQueue<T> anotherQueue) {
// YOUR CODE HERE
}
}
Question: Show the contents of two initially empty queues after each of the following statements execute. Assume a, b, x, and y are objects.
Your answer should have 11 lines that each show the contents of q1 and q2.
Put the front of the queue on the left and the back of the queue on the right.
q1.enqueue(x)
q1.enqueue(y)
q2.enqueue(a)
q2.enqueue(b)
q1.enqueue(q2.getFront())
q2.enqueue(q1.dequeue())
q2.enqueue(q1.getFront())
q2.dequeue()
q1.enqueue(q2.getFront());
q1.enqueue(q1.dequeue());
q2.enqueue(q1.getFront());
Explanation / Answer
erg 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)
{
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.