You will modify the standard stack and queue so that they do not allow duplicate
ID: 3580188 • Letter: Y
Question
You will modify the standard stack and queue so that they do not allow duplicate items and they provide a method to change the priority of a particular element. Use an array-based implementation of each data structure.
Part A: Stacks (40 points)
Implement a new kind of stack that only accepts a single copy of an object in the stack (i.e., it does not allow duplicates).
If an element is pushed onto the stack, and the element already exists in the stack, the stack will remain unchanged.
Include a method moveToTop that allows you to prioritize an element in the stack.
If invoked with an element currently in the stack, the method moves the element to the top of the stack.
If invoked with an element not in the stack, the method adds the element to the top of the stack (as would normally happen with push).
Your class extends ArrayStack and implements NoDupsPrioritizeStackInterface (provided).
The modified ArrayStack class has protected variables so you can directly access them in NoDupsPrioritizeArrayStack.
In addition to implementing the two new methods moveToTop and display, you must override push so that duplicates are not added.
Part B: Queues (60 points)
Implement a new kind of queue that only accepts a single copy of an object in the queue (i.e., it does not allow duplicates).
If an element is enqueued, and the element already exists in the queue, the queue will remain unchanged.
Include a method moveToBack that allows you to de-prioritize an element in the queue.
If invoked with an element currently in the queue, the method moves the element to the back of the queue .
If invoked with an element not in the queue , the method adds the element to the back of the queue (as would normally happen with enqueue).
Your class should implement NoDupsDePrioritizeQueueInterface (provided).
The modified ArrayQueue class has protected variables so you can directly access them in NoDupsDePrioritizeArrayQueue.
In addition to implementing the two new methods moveToBack and display, you must override enqueue so that duplicates are not added.
Notes for both parts:
Only modify the two new classes- do not change any other classes or interfaces.
Start by reviewing the provided ArrayStack/ArrayQueue classes.
Make sure you have a strong understanding of how these original classes are implemented.
Both classes use expandable arrays as the underlying data structure.
The ArrayStack class stores the bottom of the stack in the 0 position.
The ArrayQueue class uses a circular array with one unused location. The front index changes with dequeues and the back index changes with enqueues.
For full credit:
Access the underlying array directly. Do not destroy/rebuild the stack/queue each time you need to examine its entries!
Make your solution efficient by considering the front/back/top indexes. Don't examine positions if it's not necessary to do so.
Reuse code when possible.
Think about special cases (like empty and singleton stacks and queues).
I have provided two driver programs to test your code.
You might want to run additional tests to make sure your classes function correctly when the number of elements approaches capacity.
Zip all files together and upload them for submission. Include the driver programs and interface files in your zip file, even though these files were not edited.
Explanation / Answer
In this way we can implement a new kind of stack that only accepts a single copy of an object in the stack and also it doesn’t allow duplication. So let us start by programming:
public class ArrayQueue<T> implements QueueInterface<T> {
private T[] queue; // circular array of queue entries and one unused location
private int frontIndex;
private int backIndex;
private static final int DEFAULT_INITIAL_CAPACITY = 50;
public ArrayQueue()
{
this(DEFAULT_INITIAL_CAPACITY);
}
public ArrayQueue(int initialCapacity)
{
queue = (T[]) new Object[initialCapacity + 1];
frontIndex = 0;
backIndex = initialCapacity;
}
public void enqueue(T newEntry)
{
if (isArrayFull())
{
doubleArray();
}
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
}
public T getFront() {
T front = null;
if (!isEmpty())
{
front = queue[frontIndex];
}
return front;
}
public T dequeue()
{
T front = null;
if (!isEmpty())
{
front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length;
}
return front;
}
public boolean isEmpty() {
return frontIndex == ((backIndex + 1) % queue.length);
}
public void clear() {
if (!isEmpty())
{ // deallocates only the used portion
for (int index = frontIndex; index != backIndex; index = (index + 1) % queue.length)
{
queue[index] = null;
}
queue[backIndex] = null;
}
frontIndex = 0;
backIndex = queue.length - 1;
}
private boolean isArrayFull() {
return frontIndex == ((backIndex + 2) % queue.length);
}
private void doubleArray()
{
T[] oldQueue = queue;
int oldSize = oldQueue.length;
queue = (T[]) new Object[2 * oldSize];
for (int index = 0; index < oldSize - 1; index++)
{
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
}
frontIndex = 0;
backIndex = oldSize - 2;
}
}
public class NoDupsDePrioritizeQueue<T> extends ArrayQueue
implements NoDupsDePrioritizeQueueInterface<T>
{
public NoDupsDePrioritizeQueue()
{
super();
}
public NoDupsDePrioritizeQueue(int initialCapacity) {
super(initialCapacity)
}
public void moveToBack(T newEntry)
{
boolean found = false;
int start = frontIndex;
int back = backIndex;
int index = 0;
if (!isEmpty())
{
//searching if newEntry is already present in the queue. If it is present,
note its index. while (start != back) {
if (newEntry.equals(queue[start])) {
found = true;
index = start;
break;
}
start = (start + 1) % queue.length;
}
// the condition does not check queue[back] as the loop exits then.
//Hence we evaluate it separately.
if (newEntry.equals(queue[start])) {
found = true;
index = start;
}
if (found == false) {
enqueue(newEntry);
} else
{
foundValue = queue[index];
while ((index + 1) % queue.length <= backIndex) {
queue[index] = queue[(index + 1) % queue.length];
}
queue[backIndex] = foundValue;
}
} else
{
enqueue(newEntry);
}
}
// displaying the queue without destroying it
public void display() {
int start = frontIndex;
int back = backIndex;
while (start != back && !isEmpty()) {
System.out.println(queue[start]);
start = (start + 1) % queue.length;
}
System.out.println(queue[start]);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.