4.2( Just as reference): Create a Deque class based on the discussion of deques
ID: 3594078 • Letter: 4
Question
4.2( Just as reference):
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
To be done:
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
// stack.java
// demonstrates stacks
// to run this program: C>java StackApp
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize; // size of stack array
private long[] stackArray;
private int top; // top of stack
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s; // set array size
stackArray = new long[maxSize]; // create array
top = -1; // no items yet
}
//--------------------------------------------------------------
public void push(long j) // put item on top of stack
{
stackArray[++top] = j; // increment top, insert item
}
//--------------------------------------------------------------
public long pop() // take item from top of stack
{
return stackArray[top--]; // access item, decrement top
}
//--------------------------------------------------------------
public long peek() // peek at top of stack
{
return stackArray[top];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{
return (top == -1);
}
//--------------------------------------------------------------
public boolean isFull() // true if stack is full
{
return (top == maxSize-1);
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class StackApp
{
public static void main(String[] args)
{
StackX theStack = new StackX(10); // make new stack
theStack.push(20); // push items onto stack
theStack.push(40);
theStack.push(60);
theStack.push(80);
while( !theStack.isEmpty() ) // until it’s empty,
{ // delete item from stack
long value = theStack.pop();
System.out.print(value); // display it
System.out.print(“ “);
} // end while
System.out.println(“”);
} // end main()
}
You MUST USE this MAIN below:
public static void main(String[] args)
{
StackX theStack = new StackX(10); // make new stack
for(int j=0; !theStack.isFull(); j++) // push 10 items
theStack.push(j*10); // (deque wraps)
while( !theStack.isEmpty() ) // until it's empty,
{ // pop items
long value = theStack.pop();
System.out.print(value + " "); // display items
} // 90, 80, ..., 10, 0
System.out.println("");
} // end main()
The output MUST look like this:
90 80 70 60 50 40 30 20 10 0
Explanation / Answer
// Deque.java
public class Deque<T>
{
private final int DEFAULT_CAPACITY = 10;
private int left;
private int right;
private int count;
private T[] deque;
// default constructor
public Deque()
{
left = 0;
right = 0;
count = 0;
deque = (T[]) (new Object[DEFAULT_CAPACITY]);
}
// parameterized constructor
public Deque(int initialCapacity)
{
left = 0;
right = 0;
count = 0;
deque = (T[]) (new Object[initialCapacity]);
}
// insertLeft method implementation
public void insertLeft(T element)
{
if(size() == deque.length)
{
System.out.println("The deque is full.");
return;
}
if(left == 0)
left = deque.length - 1;
else
left = (left - 1) % deque.length;
deque[left] = element;
count++;
}
// insertRight method implementation
public void insertRight(T element)
{
if(size() == deque.length)
{
System.out.println("The deque is full.");
return;
}
deque[right] = element;
right = (right + 1) % deque.length;
count++;
}
// removeLeft method implementation
public T removeLeft()
{
if(isEmpty())
{
System.out.println("Deque is empty!");
return null;
}
T result = deque[left];
deque[left] = null;
left = (left + 1) % deque.length;
count--;
return result;
}
// removeRight method implementation
public T removeRight()
{
if(isEmpty())
{
System.out.println("Deque is empty!");
return null;
}
T result = deque[right - 1];
deque[right - 1] = null;
right = (right - 1) % deque.length;
count--;
return result;
}
// isEmpty method implementation
public boolean isEmpty()
{
return (count == 0);
}
// isFull method implementation
public boolean isFull()
{
return (count == deque.length);
}
// isFull method implementation
public int size()
{
return count;
}
// getLeft method implementation
public T getLeft()
{
if(isEmpty())
{
System.out.println("Deque is empty!");
return null;
}
T result = deque[left];
return result;
}
// getRight method implementation
public T getRight()
{
if(isEmpty())
{
System.out.println("Deque is empty!");
return null;
}
T result = deque[right - 1];
return result;
}
// toString method implementation
public String toString()
{
String queueElements = "";
for(int i = left, j = 0; j < count; i = (i + 1) % deque.length, j++)
{
queueElements = queueElements + deque[i].toString() + " ";
}
return queueElements;
}
} // end of Deque class
-------------------------------------------------------
// DequeTest.java
public class DequeTest
{
// start main method
public static void main(String[] args)
{
// create an object for CircularArrayDeque class
Deque<Integer> deq = new Deque<Integer>();
// add integers to the deque at right
deq.insertRight(25);
deq.insertRight(15);
deq.insertRight(30);
deq.insertRight(10);
// add integers to the deque at left
deq.insertLeft(35);
deq.insertLeft(20);
// call all the methods to test them
System.out.println("The deque is empty.(T/F): " + deq.isEmpty());
System.out.println("The deque is full.(T/F): " + deq.isFull());
System.out.println("The size of the deque: " + deq.size());
System.out.println("The elements in the deque are: " + deq.toString());
System.out.println("The element at the left of the deque: " + deq.getLeft());
System.out.println("The element at the right of the deque: " + deq.getRight());
System.out.println("The removed element from the right: " + deq.removeRight());
System.out.println("The removed element from the left: " + deq.removeLeft());
System.out.println("The elements in the deque are: " + deq.toString());
} // end main
} // end of DequeTest class
Sample Output:
The deque is empty.(T/F): false
The deque is full.(T/F): false
The size of the deque: 6
The elements in the deque are: 20 35 25 15 30 10
The element at the left of the deque: 20
The element at the right of the deque: 10
The removed element from the right: 10
The removed element from the left: 20
The elements in the deque are: 35 25 15 30
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.