这是我到目前为止编写的代码，但测试一直失败，如果有人可以提供帮助，我可以提供测试文件。谢谢你！
要求前部应从位置 0 开始，后部应从位置长度 -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;
}
}
}
import java.util.*;
class MyCircularDeque {
private int[] deque;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularDeque(int k) {
capacity = k + 1; // Use one extra space to differentiate between full and empty
deque = new int[capacity];
front = 0;
rear = 0;
size = 0;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
front = (front - 1 + capacity) % capacity; // Move front circularly
deque[front] = value;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
deque[rear] = value;
rear = (rear + 1) % capacity; // Move rear circularly
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity; // Move front circularly
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
rear = (rear - 1 + capacity) % capacity; // Move rear circularly
size--;
return true;
}
public int getFront() {
if (isEmpty()) {
return -1;
}
return deque[front];
}
public int getRear() {
if (isEmpty()) {
return -1;
}
return deque[(rear - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity - 1;
}
}
说明：
我们使用固定大小 k + 1 来初始化双端队列以区分 使用圆形数组的满状态和空状态。指针前面 后部从索引 0 开始。
insertFront：将前指针向后移动一步（循环） 并插入元素。 insertLast：将元素插入到 当前后索引并将后指针向前移动一步 （循环）。
deleteFront：将前指针向前移动一步（循环）至 删除该元素。 deleteLast：将后指针移动一步 向后（循环）删除元素。
getFront：返回front指针处的元素。 getRear：返回后 - 1 位置的元素，始终为后 指向最后一个元素之后的下一个可用位置。
isEmpty：检查双端队列的大小是否为0。 isFull：检查是否已满 双端队列已达到其容量（大小 = 容量 - 1）。
时间复杂度： 每个操作（插入、删除和访问）都需要 O(1) 时间，因为我们只是调整指针或访问元素。
空间复杂度： 空间复杂度为 O(k)，其中 k 是双端队列的最大大小，因为我们使用长度为 k + 1 的固定大小数组。