Hi,

I am taking a Data Structures and Algorithms class in Java this semester. We were just introduced to Stacks and Queues. The assignment I am working on has multiple parts. I have attached the description of the problem along with the code needed for the assignment. There are also notes about this assignment from the professor which are important to follow.

Thanks!

Assignment:

Notes from the professor:

1.) Your class Deque in Assignment 2 should look like this:

class Deque

{

private int maxSize;

private long[] dekArray;

private int left;

private int right;

private int nItems;

//--------------------------------------------------------------

public Deque(int s) // constructor

{

maxSize = s;

dekArray = new long[maxSize];

int center = maxSize/2 - 1;

left = center+1; // left and right

right = center; // start out "crossed"

nItems = 0;

}

// other methods

}

2.) How to test class Deque?

You do not need to define a print method to test Deque. Just use insert and remove methods themselves.

For example,

when you call insertLeft three times on 1, 2, 3; then call removeLeft three times, you should get 3, 2,1.

when you call insertLeft three times on 1, 2, 3; then call removeRight three times, you should get 1, 2, 3.

Similar to insertRight method.

3.) Problem 2 and Problem 3 of Assignment 2

When you define class QueueD and class StackD, you only need a Deque as data member to store data in queue or stack. You do not need to define other array as data member because Deque itself has an array for storing data. Definition looks like:

public class QueueD {

private Deque dq;

//constructor and other methods

}

Then, you will use dq to call Deque's method to implement QueueD's insert/remove and StackD's push/pop.

Sample Code for QueueX:

package queue;

public class QueueX {

private int maxSize;

private T[] queArray;

private int front; //front of the queue

private int rear; //rear of the queue

private int nItems;

//--------------------------------------------------------------

public QueueX(int s) // constructor

{

maxSize = s;

queArray = (T[])new Object[maxSize];

front = 0;

rear = -1;

nItems = 0;

}

//--------------------------------------------------------------

public void insert(T item) // put item at rear of queue

{

if(rear == maxSize-1) // deal with wraparound

rear = -1;

queArray[++rear] = item; // increment rear and insert

nItems++; // one more item

}

//--------------------------------------------------------------

public T remove() // take item from front of queue

{

T temp = queArray[front++]; // get value and increment front

if(front == maxSize) // deal with wraparound

front = 0;

nItems--; // one less item

return temp;

}

//--------------------------------------------------------------

public T peek() // 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 QueueX

Sample Code for StackX:

package stack;

public class StackX

{

private int maxSize; // size of stack array

private T[] stackArray;

private int top; // top of stack

//--------------------------------------------------------------

public StackX(int s) // constructor

{

maxSize = s; // set array size

stackArray = (T[])new Object[maxSize]; // create array

top = -1; // no items yet

}

//--------------------------------------------------------------

public void push(T j) // put item on top of stack

{

stackArray[++top] = j; // increment top, insert item

}

//--------------------------------------------------------------

public T pop() // take item from top of stack

{

return stackArray[top--]; // access item, decrement top

}

//--------------------------------------------------------------

public T 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

1. Create a Deque class based on the discussion of deques (double-ended queues). It should include inssxtlaft), insextRiaht), xemxeett),uaxeRiaht), peekRight ), reekleft), isEmptyx ), andisEuli ) methods. It will need to support wraparound at the end of the array, as queues do. Write a dr test class Deque. iver class DecueApp to 2. In the lectures (textbook), we used an array to implement a queue class queue Here you are asked to implement a queue class gueueD that is based on the Deque class defined in Problem 1. It means you need to use composition and make QueueD has-a Deque. This queue class should have the same methods and capabilities as thex class. Write a driver class ueuepp to test class QueueD 3. In the lectures (textbook), we used an array to implement a stack class sta Write a program that implements a stack class taakR that is based on the Deque class defined in Problem 1. Similarly, composition is need to define StackD. This stack class should have the same methods and capabilities as the Stackx class. Write a driver class StackDApp to test class StackD