Это то, что я до сих пор писал, но тесты продолжают проваливаться, я могу предоставить тестовый файл, если кто-то может помочь. благодарю вас!
Требования состоят в том, чтобы фронт начинался с нулевого положения, а задний - с длины -1.
Также в пустой очереди задняя часть находится на одну позицию против часовой стрелки вперед и в полной очереди, задняя - на две позиции против часовой стрелки вперед.
В нашей реализации Dequeue нет переменной count для отслеживания количества элементов. Вместо этого, чтобы отличить полную очередь от пустой очереди, мы никогда не позволяем очереди заполняться полностью.
Полная очередь - это очередь с ровно одним пустым местом в массиве. Таким образом, мы можем различить пустую очередь и полную очередь, посмотрев на относительные положения спереди и сзади.
import java.util.*;
public class Dequeue<E> {
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[i] = 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[i] = 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<E> iterator(){
return new myIterator();
}
/**private inner class to implement the Iterator<E> interface
*
*/
public class myIterator implements Iterator<E> {
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;
}
}
}