Implement a generic array based on FIFO Queue that contains the following attrib
ID: 3919638 • Letter: I
Question
Implement a generic array based on FIFO Queue that contains the following attributes and operations:
-size: # of elements in this queue, 0 when queue is empty
-front: index of the front element
-back: index of the back element
-CAPACITY= 10: initial length of the container
-container: generic array, initially at given capacity
OPERATION:
-enqueue: insert a new element at the back of this queue. if array container is full, the container should be expanded by creating a new larger container, and preserving all the elements of the queue in FIFO
-dequeue: remove the element at the front of this queue, return null if queue is empty. All remaining elements of the container should be shifted one postion towards the front during dequeu.
-isEmpty: return true if this queue has no elements, otherwise return false
-peek: return the front element of this queue, return null if this queue is empty
Explanation / Answer
Solution
public class ArrayQueue implements Queue
{
/**
* Construct the queue.
*/
public ArrayQueue( )
{
theArray = new Object[ DEFAULT_CAPACITY ];
makeEmpty( );
}
/**
* Test if the queue is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return currentSize == 0;
}
/**
* Make the queue logically empty.
*/
public void makeEmpty( )
{
currentSize = 0;
front = 0;
back = -1;
}
/**
* Return and remove the least recently inserted item
* from the queue.
* @return the least recently inserted item in the queue.
* @throws UnderflowException if the queue is empty.
*/
public Object dequeue( )
{
if( isEmpty( ) )
throw new UnderflowException( "ArrayQueue dequeue" );
currentSize--;
Object returnValue = theArray[ front ];
front = increment( front );
return returnValue;
}
/**
* Get the least recently inserted item in the queue.
* Does not alter the queue.
* @return the least recently inserted item in the queue.
* @throws UnderflowException if the queue is empty.
*/
public Object peek( )
{
if( isEmpty( ) )
throw new UnderflowException( "ArrayQueue getFront" );
return theArray[ front ];
}
/**
* Insert a new item into the queue.
* @param x the item to insert.
*/
public void enqueue( Object x )
{
if( currentSize == theArray.length )
doubleQueue( );
back = increment( back );
theArray[ back ] = x;
currentSize++;
}
/**
* Internal method to increment with wraparound.
* @param x any index in theArray's range.
* @return x+1, or 0 if x is at the end of theArray.
*/
private int increment( int x )
{
if( ++x == theArray.length )
x = 0;
return x;
}
/**
* Internal method to expand theArray.
*/
private void doubleQueue( )
{
Object [ ] newArray;
newArray = new Object[ theArray.length * 2 ];
// Copy elements that are logically in the queue
for( int i = 0; i < currentSize; i++, front = increment( front ) )
newArray[ i ] = theArray[ front ];
theArray = newArray;
front = 0;
back = currentSize - 1;
}
private Object [ ] theArray;
private int currentSize;
private int front;
private int back;
private static final int DEFAULT_CAPACITY = 10;
}
public class UnderflowException extends RuntimeException
{
/**
* Construct this exception object.
* @param message the error message.
*/
public UnderflowException( String message )
{
super( message );
}
}
public interface Queue
{
/**
* Insert a new item into the queue.
* @param x the item to insert.
*/
void enqueue( Object x );
/**
* Get the least recently inserted item in the queue.
* Does not alter the queue.
* @return the least recently inserted item in the queue.
* @exception UnderflowException if the queue is empty.
*/
Object getFront( );
/**
* Return and remove the least recently inserted item
* from the queue.
* @return the least recently inserted item in the queue.
* @exception UnderflowException if the queue is empty.
*/
Object dequeue( );
/**
* Test if the queue is logically empty.
* @return true if empty, false otherwise.
*/
boolean isEmpty( );
/**
* Make the queue logically empty.
*/
void makeEmpty( );
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.