On pages 138-142(Listing 4.4 and Listing 4.5), the textbook by Lafore gives two
ID: 671621 • Letter: O
Question
On pages 138-142(Listing 4.4 and Listing 4.5), the textbook by Lafore gives two implementations of a queue of values of type long stored in an array. These implementations are correct as far as they go, but they have some weaknesses. They use more instance variables than necessary, they do not re-dimension the array if it gets full, insertion into a full queue wipes out one of the values in the queue, and removal of a value from an empty queue can return a previously removed value with no warning that an incorrect value is being returned.
For this assignment, you are to write a queue class that fixes these weaknesses. The only instance variables should be queArray[], front, and rear (see page 141).
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[] .
LISTING 4.4 The queue.java Program
// queue.java
// demonstrates queue
// to run this program: C>java QueueApp
//////////////////////////////////////////////////////////////// class Queue
{ private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//--------------------------------------------------------------
public Queue(int s) // constructor
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//--------------------------------------------------------------
public void insert(long j) // put item at rear of queue
{
if(rear == maxSize-1) // deal with wraparound
rear = -1;
queArray[++rear] = j; // increment rear and insert
nItems++; // one more item
}
//--------------------------------------------------------------
public long remove() // take item from front of queue
{
long temp = queArray[front++]; // get value and incr front
if(front == maxSize) // deal with wraparound
front = 0;
nItems--; // one less item
return temp;
}
//--------------------------------------------------------------
public long peekFront() // peek at front of queue
{
return queArray[front];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return (nItems==0);
}
//--------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return (nItems==maxSize);
}
//--------------------------------------------------------------
public int size() // number of items in queue
{
return nItems;
}
//--------------------------------------------------------------
} // end class Queue ////////////////////////////////////////////////////////////////
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // remove and display
{ // all items
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(“ “);
}
System.out.println(“”);
} // end main()
} // end class QueueApp
LISTING 4.5 The Queue Class Without nItems
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
//--------------------------------------------------------------
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
Please find the Modified solution:
class Queue {
private long[] queArray;
private int front;
private int rear;
// --------------------------------------------------------------
public Queue() // constructor
{
front = -1;
rear = -1;
}
// --------------------------------------------------------------
public void insert(long j) // put item at rear of queue
{
int i = 0;
if (front == -1) {
queArray = new long[1];
front = 0;
rear = 0;
queArray[0] = j;
} else {
long[] newArray;
newArray = new long[queArray.length + 1];
i = front;
for (; (i < queArray.length); i++) {
newArray[i] = queArray[i];
}
newArray[i] = j;
rear = i;
queArray = newArray;
}
}
// --------------------------------------------------------------
public long remove() // take item from front of queue
{
if (rear < front) {
front = -1;
rear = -1;
}
long temp = queArray[front];
front++;
return temp;
}
// --------------------------------------------------------------
public long peekFront() // peek at front of queue
{
return queArray[front];
}
// --------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return rear < front;
}
} // end class Queue
// ////////////////////////////////////////////////////////////////
class QueueApp {
public static void main(String[] args) {
Queue theQueue = new Queue(); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while (!theQueue.isEmpty()) // remove and display
{ // all items
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
} // end main()
} // end class QueueApp
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.