4.1 Write a method for the Queue class in the queue.java program (Listing 4.4) t
ID: 3565837 • Letter: 4
Question
4.1
Write a method for the Queue class in the queue.java program (Listing 4.4) that displays the contents of the queue. Note that this does not mean simply displaying the contents of the underlying array. You should show the queue contents from the first item inserted to the last, without indicating to the viewer whether the sequence is broken by wrapping around the end of the array. Be careful that one item and no items display properly, no matter where front and rear are.
Listing 4.4 is below
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//
public Queue(int s)
{
maxSize = s;
queArray = new long[maxSize];
front =0;
rear = -1;
nItems = 0;
}
//
public void insert(long j)
{
if(rear == maxSize -1)
rear = -1;
queArray[++rear] = j;
nItems++;
}
//
public long remove()
{
long temp = queArray[front++];
if(front == maxSize)
front = 0;
nItems--;
return temp;
}
//
public long peekFront()
{
return queArray[front];
}
//
public boolean isEmpty()
{
return(nItems==0);
}
//
public boolean isFull()
{
return (nItems==maxSize);
}
//
public int size()
{
return nItems;
}
//
} //end class
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() )
{
long n = theQueue.remove();
System.out.print(n);
System.out.print( " ");
}
System.out.println(" ");
} //end main()
} //end class
4.2
Create a Deque class based on the discussion of deques (double-ended queues) in this chapter. It should include insertLeft(), insertRight(), removeLeft(), removeRight(), isEmpty(), and isFull() methods. It will need to support wraparound at the end of the array, as queues do.
4.3
Write a program that implements a stack class that is based on the Deque class in the Programming Project 4.2. This stack class should have the same methods and capabillities as the StackX class in the stack.java program (Listing 4.1).
Listing 4.1 is below
class StackX
{
private int maxSize;
private long[] stackArray;
private int top;
//
public stackX(int s)
{
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
//
public void push(long j)
{
stackArray[++top] = j;
}
//
public long pop()
{
return stackArray[top --];
}
//
public long peek()
{
return stackArray[top];
}
//
public boolean isEmpty()
{
return (top == -1);
}
//
public boolean isFull()
{
return (top == maxSize-1);
}
//
} //end class StackX
class StackApp
{
public static void main(String[] args)
{
StackX the Stack = new StackX(10);
theStack.push(20);
theStack.push(40);
theStack.push(60);
theStack.push(80);
while( !theStack.isEmpty() )
{
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
} //end while
System.out.println(" ");
} //end main
} //end class
Explanation / Answer
Exercise 4.1 : display() method in Queue class and testing it in QueueApp
Queue.java
class Queue {
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//
public Queue(int s) {
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//
public void insert(long j) {
if (rear == maxSize - 1)
rear = -1;
queArray[++rear] = j;
nItems++;
}
//
public long remove() {
long temp = queArray[front++];
if (front == maxSize)
front = 0;
nItems--;
return temp;
}
//
public long peekFront() {
return queArray[front];
}
//
public boolean isEmpty() {
return (nItems == 0);
}
//
public boolean isFull() {
return (nItems == maxSize);
}
//
public int size() {
return nItems;
}
public void display(){
for(int i = 1, idx = front; i <= nItems; i++)
{
System.out.print(" " + queArray[idx]);
idx++;
if(idx == maxSize)
idx = 0;
}
System.out.println();
}
//
} // end class
QueueApp.java
public class QueueApp {
public static void main(String[] args) {
Queue theQueue = new Queue(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.display();
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.display();
theQueue.insert(50);
theQueue.insert(60);
theQueue.insert(70);
theQueue.insert(80);
theQueue.display();
while (!theQueue.isEmpty()) {
long n = theQueue.remove();
System.out.print(n);
System.out.print(" ");
}
System.out.println(" ");
} // end main()
} // end class
output
10 20 30 40
40
40 50 60 70 80
40 50 60 70 80
Exercise 4.2: Deque class implementation and testing
Deque.java
class DeQueue {
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//
public DeQueue(int s) {
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//
public void insertLeft(long j) {
if(isFull()) //can not insert if already full
return;
if (front == 0)
front = maxSize;
queArray[--front] = j;
nItems++;
}
//
public void insertRight(long j) {
if(isFull()) //can not insert if already full
return;
if (rear == maxSize - 1)
rear = -1;
queArray[++rear] = j;
nItems++;
}
//
public long removeLeft() {
if(isEmpty())
return -1;
long temp = queArray[front++];
if (front == maxSize)
front = 0;
nItems--;
return temp;
}
//
public long removeRight() {
if(isEmpty())
return -1;
long temp = queArray[rear--];
if (rear == -1)
rear = maxSize - 1;
nItems--;
return temp;
}
//
public long peekFront() {
return queArray[front];
}
public long peekRear() {
return queArray[rear];
}
//
public boolean isEmpty() {
return (nItems == 0);
}
//
public boolean isFull() {
return (nItems == maxSize);
}
//
public int size() {
return nItems;
}
public void display(){
for(int i = 1, idx = front; i <= nItems; i++)
{
System.out.print(" " + queArray[idx]);
idx++;
if(idx == maxSize)
idx = 0;
}
System.out.println();
}
//
} // end class
DequeApp.java
public class DequeApp {
public static void main(String[] args) {
DeQueue theQueue = new DeQueue(5);
theQueue.insertLeft(10);
theQueue.insertLeft(20);
theQueue.insertRight(30);
theQueue.insertRight(40);
theQueue.display();
theQueue.removeLeft();
theQueue.removeLeft();
theQueue.display();
theQueue.insertRight(50);
theQueue.insertRight(60);
theQueue.insertRight(70);
theQueue.insertRight(80);
theQueue.display();
while (!theQueue.isEmpty()) {
long n = theQueue.removeRight();
theQueue.display();
}
System.out.println(" ");
} // end main()
} // end class
output
20 10 30 40
30 40
30 40 50 60 70
30 40 50 60
30 40 50
30 40
30
Exercise 4.3: Stack class based on Deque class and testing
Stack.java
class Stack
{
DeQueue deque;
//
public Stack(int s) {
deque = new DeQueue(s);
}
//
public void push(long j) {
deque.insertLeft(j);
}
//
public long pop() {
return deque.removeLeft();
}
//
public long peek() {
return deque.peekFront();
}
//
public boolean isEmpty() {
return deque.isEmpty();
}
//
public boolean isFull() {
return deque.isFull();
}
public void display(){
deque.display();
}
//
} // end class Stack
StackTest.java
public class StackTest {
public static void main(String[] args) {
Stack theStack = new Stack(10);
theStack.push(20);
theStack.push(40);
theStack.push(60);
theStack.push(80);
theStack.display();
while (!theStack.isEmpty()) {
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
} // end while
System.out.println(" ");
} // end main
} // end class
output
80 60 40 20
80 60 40 20
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.