JAVA/OOP Deque Implementiong with Circular Array For this exercise, implement a
ID: 3680480 • Letter: J
Question
JAVA/OOP Deque Implementiong with Circular Array
For this exercise, implement a deque of Strings. Formally support the following operations:
constructor: initialize an empty deque
insertOnFront: insert a given String on the front of the deque
deleteFromFront: return (and delete) the String extracted from the front of the deque
insertOnBack: insert given String on the back of
the deque
deleteFromBack: return (and delete) the String extracted from the back of the deque
isEmpty: return true if the deque is empty, and false otherwise
toString: return a String summarizing the entire contents of the deque (from front to back)
toStore: return a String summarizing the entire contents of deque stotage (from array index 0 to length-1)
1. Write a simple test program to exercise all of these operations on two instances of Deques. Construct an empty instance of each of these, then allow the user to repeatedly perform selected operations on either of the two, in any order, until they choose to quit. For each action, let the user select which Deque to manipulate, then allow them to choose from a menu of the available operations. Prompt for any necessary input, and display results of each operation (or a simple message acknowledging completuong if there is no result).
2. Use a single array of Strings to store the Deque. Give it an initial size of 5 (admittedly small, for convenient testing), but allow it to grow, if necessary. If the user asks to insert an element in a Deque that is full, allocate an array twice the current size, copy the contents of the old array to the new one (you will actually be copying the references), and carry out the requested insertion. If the user requests a deletion from an empty deque, just ignore the request without comment (The isEmpty methos is available to enable the user to detect that exceptional case).
3. Use the 'circular' array implementation strategy. Allocate a single array (with wrap-around figuratively connecting the two ends of the array) to store the deque's contents and respond to all insertion and deletion operations. Do not attempt to maintain two distinct regions within the array for separate processing of front and back operations.
Explanation / Answer
PROGRAM:
public class ArrayDeque
{
public static final int INIT_CAPACITY = 8;
protected int capacity;
protected int front;
protected int rear;
protected int[] A;
public ArrayDeque( )
{
A = new int[ INIT_CAPACITY ];
capacity = INIT_CAPACITY;
front = rear = 0;
}
public int size( )
{
return rear - front;
}
public boolean isEmpty( )
{
return front == rear;
}
public int getFirst() throws EmptyDequeException
{
if(isEmpty())
{
throw new EmptyDequeException("Deque is empty.");
}
return A[front % capacity];
}
public int getLast( ) throws EmptyDequeException
{
if(isEmpty())
{
throw new EmptyDequeException("Deque is empty.");
}
return A[(front + rear - 1) % capacity];
}
public void insertFirst( int e )
{
rear++;
if(size() == capacity)
{
capacity *= 2;
}
int[] B = new int[capacity];
for(int i = 0; i < size(); i++)
{
B[i] = A[i];
}
A = B;
for(int i = size(); i >= front; i--)
{
A[i+1] = A[i];
}
A[front] = e;
front = front % capacity;
}
public void insertLast( int e )
{
if(size() == capacity)
{
capacity *= 2;
A[rear++] = e;
}
else
{
A[rear++] = e;
}
rear++;
}
public int removeFirst( ) throws EmptyDequeException
{
if(size() == 0)
{
throw new EmptyDequeException("Deque is empty.");
}
if(capacity >= 8)
{
if(size() < capacity/4)
{
capacity /= 2;
}
}
int[] B = new int[capacity];
for(int i = 1; i < size(); i++)
{
B[i-1] = A[i];
}
A = B;
return A[front];
}
public int removeLast( ) throws EmptyDequeException
{
if(size() == 0)
{
throw new EmptyDequeException("Deque is empty.");
}
if(capacity >= 8)
{
if(size() < capacity/4)
{
capacity /= 2;
}
}
int[] B = new int[capacity];
for(int i = front; i<size()-1; i++)
{
B[i] = A[i];
}
A = B;
rear--;
return A[rear];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.