Write a queue class that fixes these weaknesses. The only instance variables sho
ID: 670560 • Letter: W
Question
Write a queue class that fixes these weaknesses. The only instance variables should be queArray[], front, and rear.
Initially, and any time the queue becomes empty, your code must set front and rear both equal to -1 .
If queArray[] is full when an insert operation is requested, re-dimension queArray[] larger and, if necessary, change the values of front and/or rear correctly before inserting the new value into the queue. If done correctly, the code will handle any insertion operation correctly, with no possibility of an error occurring, and there will not be any need for an isFull method or for a size method.
If a remove operation is requested when the queue is empty, your code should either throw an exception or it should print an error message and terminate using System.exit(0)
Test your code thoroughly, including at least one insert operation when queArray[] is full and front is greater than zero. For each queue operation in your tests, print the operation requested, and after the operation has been performed, print the values of front, rear, and the entire contents of queArray[] .
class Queue {
private int maxSize;
private long[] queArray;
private int rear;
private int front;
//------------------------------------------------------
public Queue (int s) //constructor
{
maxSize = s+1; // array is 1 cell larger
queArray = new long[maxSize]; // than requested
front = 0;
rear = -1;
}
//---------------------------------------------------------
public void insert (long j) // put item at rear of queue
{
if(rear == maxSize-1)
rear = -1;
queArray[++rear] = j;
}
//----------------------------------------------------------
public long remove() // take item from front of queue
{
long temp = queArray[front++];
if(front == maxSize)
front = 0;
return temp;
}
//----------------------------------------------------------
public long peek() // peek at front of queue
{
return queArray[front];
}
//----------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return (rear+1==front || (front + maxSize -1==rear) );
}
//--------------------------------------
public boolean isFull() // true if queue is full
{
return (rear+2==front || (front+maxSize-2==rear));
}
//--------------------------------------------------------
public int size() //(assumes queue not empty)
{
if(rear >= front) // contiguous sequence
return rear-front+1;
else // broken sequence
return(maxSize-front) + (rear+1);
}
//---------------------------------------------------------
} // end class Queue
Explanation / Answer
public class DynamicQueueImpl {
private int capacity = 2;
int queueArr[];
int front = 0;
int rear = -1;
int currentSize = 0;
public DynamicQueueImpl(){
queueArr = new int[this.capacity];
}
public void enqueue(int item) {
if (isQueueFull()) {
System.out.println("Queue is full, increase capacity...");
increaseCapacity();
}
rear++;
if(rear >= queueArr.length && currentSize != queueArr.length){
rear = 0;
}
queueArr[rear] = item;
currentSize++;
System.out.println("Adding: " + item);
}
/**
* this method removes an element from the top of the queue
*/
public void dequeue() {
if (isQueueEmpty()) {
System.out.println("Underflow ! Unable to remove element from Queue");
} else {
front++;
if(front > queueArr.length-1){
System.out.println("removed: "+queueArr[front-1]);
front = 0;
} else {
System.out.println("removed: "+queueArr[front-1]);
}
currentSize--;
}
}
/**
* This method checks whether the queue is full or not
* @return boolean
*/
public boolean isQueueFull(){
boolean status = false;
if (currentSize == queueArr.length){
status = true;
}
return status;
}
/**
* This method checks whether the queue is empty or not
* @return
*/
public boolean isQueueEmpty(){
boolean status = false;
if (currentSize == 0){
status = true;
}
return status;
}
private void increaseCapacity(){
//create new array with double size as the current one.
int newCapacity = this.queueArr.length*2;
int[] newArr = new int[newCapacity];
//copy elements to new array, copy from rear to front
int tmpFront = front;
int index = -1;
while(true){
newArr[++index] = this.queueArr[tmpFront];
tmpFront++;
if(tmpFront == this.queueArr.length){
tmpFront = 0;
}
if(currentSize == index+1){
break;
}
}
//make new array as queue
this.queueArr = newArr;
System.out.println("New array capacity: "+this.queueArr.length);
//reset front & rear values
this.front = 0;
this.rear = index;
}
public static void main(String a[]){
DynamicQueueImpl queue = new DynamicQueueImpl();
queue.enqueue(4);
queue.dequeue();
queue.enqueue(56);
queue.enqueue(2);
queue.enqueue(67);
queue.dequeue();
queue.enqueue(24);
queue.enqueue(98);
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.enqueue(435);
queue.dequeue();
queue.dequeue();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.