Я пытаюсь реализовать циклический массив в Java ⇐ JAVA

[Anonymous]

Это то, что я написал на данный момент, но тесты продолжают терпеть неудачу. Я могу предоставить тестовый файл, если кто-то может помочь. Спасибо!

Требования заключаются в том, что передняя часть должна начинаться с нулевой позиции, а задняя - с длины позиции -1.

Также в пустой очереди задняя часть занимает одну позицию против часовой стрелки вперед, а в полной очереди задняя часть — это две позиции против часовой стрелки вперед.

В нашей реализации Dequeue нет переменной count для отслеживания количества элементов. Вместо этого, чтобы отличить полную очередь от пустой, мы никогда не допускаем полного заполнения очереди.

Полная очередь — это очередь, в массиве которой имеется ровно одно пустое место. Таким образом, мы можем отличить пустую очередь от полной, посмотрев на относительное положение передней и задней части.

import java.util.*;
public class Dequeue {
private E elements[];
private int front, rear;
private static final int INITIAL_CAPACITY = 5;

/**Creates an empty dequeue
*/

@SuppressWarnings("unchecked")
public Dequeue() {
elements = (E[]) new Object[INITIAL_CAPACITY];
front = 0;
rear = elements.length-1; // rear will point one position counter clockwise front
}
/** Increases the size of the queue when the queue is full
*
*/

@SuppressWarnings("unchecked")
private void reallocate() {
E[] queue = (E[]) new Object[INITIAL_CAPACITY *10 ]; // expand the size of the queue by creating a new queue with size 10 times the initial size
int current = front; // local pointer pointing at front
for (int i = 0; i < elements.length; i++) {
queue = elements[current]; // new queue gets all the elements of the old queue
current = (current + 1) % elements.length; // pointer moves to the next queue spot, clockwise
}
front = 0;
rear = elements.length-1;
elements = queue;
}

/** Adds an item to the front of this dequeue
* @param anEntry the item to be placed at the front of the dequeue.
* @return true (always successful)
* Precondition:None
* Postcondition: the new item is the first item on the dequeue
*/

public boolean addFront(E anEntry) {
if (size() == elements.length - 1) { // check if queue is full
reallocate();
}
else if(empty()) {
elements[front] = anEntry;
front = (front + 1) % elements.length;
return true;}
else {
if (front == rear) {
front = (rear +1)%elements.length +1;

}
elements[front] = anEntry;
front = (front + 1) % elements.length;

return true;
}

}

/** Adds an item to the rear of this dequeue
* @param anEntry - is the item to be placed at the end of the dequeue.
* @return true (always successful)
* Precondition:None
* Postcondition:the new item is the last item on the dequeue
*/

@SuppressWarnings("unchecked")
public boolean addRear(E anEntry) {
if (size() == elements.length - 1) {
E[] queue = (E[]) new Object[INITIAL_CAPACITY * 10];
int current = front;
for (int i = 0; i < size(); i++) {
queue = elements[current];
current = (current + 1) % elements.length;
}
front = 0;
rear = size() + 1;
elements = queue;
}
if (empty()) {
rear = front = 0;
elements[rear] = anEntry;
}
else {
rear = (rear + 1) % elements.length; //moves clockwise
elements[rear] = anEntry;
}
return true;
}

/** Removes the item from the front of the dequeue
* @return The front item from the dequeue.
* @throws NoSuchElementException if the dequeue is empty
* Precondition: The dequeue is not empty
* Postcondition:The front item on the dequeue has been removed and the dequeue has one less element
*/
public E removeFront() {
if (empty()) throw new NoSuchElementException();
E item;
if (size() == 1) {
item = elements[front];//stores the front element
rear = -1;
front = 0;
}
else {
item = elements[front];
front = (front + 1) % elements.length; //moves clockwise, element is now removed
}
return item;
}

/** Removes the item from the back of the dequeue
* @return The last item from the dequeue.
* @throws NoSuchElementException if the dequeue is empty
* Precondition: the dequeue is not empty
* Postcondition: the last item on the dequeue has been removed and the dequeue has one less element
*/

public E removeRear() {
if (empty()) throw new NoSuchElementException();
E item;
if (size() == 1) {
item = elements[rear]; //stores the rear element
front = 0;
rear = -1; //element now removed
}
else if (rear == 0) {
item = elements[rear];
rear = elements.length; //element now removed

}
else {
item = elements[rear];
rear -= 1; //moves counter clockwise, element removed
}
return item;
}

/** Returns the object at the front of the dequeue without removing it from the dequeue
* @return the object at the front of the dequeue if the dequeue is not empty
* @throws NoSuchElementException - if the dequeue is empty.
* Precondition: none
* Postcondition: The dequeue remains unchanged
*/

public E peekFront() {
if (empty())
throw new NoSuchElementException();
else {
return elements[front];
}
}

/** Returns the object at the rear of the dequeue without removing it from the dequeue.
* @return the object at the back of the dequeue if the dequeue is not empty.
* @throws NoSuchElementException if the dequeue is empty.
* Precondition: none
* Postcondition: The dequeue remains unchanged.
*/

public E peekRear() {
if (empty()) throw new NoSuchElementException();
else {
return elements[rear];
}
}

/** Checks if dequeue is empty
* @return true if the dequeue is empty; false otherwise.
*/

public boolean empty() {
return ((rear + 1)% elements.length == front);
}

/**
* @return the number of elements in this dequeue.
*/

public int size() {
if (empty())
return 0;
else {
if(front>rear) {
return(((elements.length - front) + (rear + 1)) % elements.length);

}else if(rear>=front) { return ((rear -front + 1)% elements.length);}

}
}

/**
* @return an iterator for the dequeue.
*/
public Iterator iterator(){
return new myIterator();
}

/**private inner class to implement the Iterator interface
*
*/
public class myIterator implements Iterator {
private int forward;
/**
* Initializes the myIterator object to reference the first dequeue
* element
*/
public myIterator() {
forward = front;
}

/**Returns true if there are more elements in the dequeue to access
* else return false
*
*/
public boolean hasNext() {
if (forward == (rear + 1) % elements.length)
return false;
return true;
}

/**Returns the next element in the queue
* pre: forward references the next
* element to access
* post: forward is incremented by the remainder
* @return The element with subscript value
*
*/
public E next() {
if (!hasNext())
throw new NoSuchElementException();
E returnValue = elements[forward];
forward = (forward + 1) % elements.length;
return returnValue;
}
}
}


Подробнее здесь: https://stackoverflow.com/questions/586 ... ue-in-java