使用循环数组实现双端队列？

Question

我在使用循环数组实现这个双端队列时遇到了很多麻烦；特别是，无论我尝试什么，删除方法似乎都会删除错误的元素。有人可以帮忙吗？

public class ArrayDeque
{
   public static final int INIT_CAPACITY = 8;   // initial array capacity
   protected int capacity;  // current capacity of the array
   protected int front;     // index of the front element
   protected int rear;      // index of the rear element
   protected int[] A;       // array deque

   public ArrayDeque( )      // constructor method
   {
      A = new int[ INIT_CAPACITY ];
      capacity = INIT_CAPACITY;
      front = rear = 0;
    }

   /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size( )
    {
        return rear - front;
    }

    /**
     * Returns true if this collection is empty.
     * @return true if this collection is empty.
     */ 
    public boolean isEmpty( )
    {
        return front == rear;
    }
    /**
     * Returns the first element of the deque
     */
    public int getFirst() throws EmptyDequeException
    {     
        if(isEmpty()){
            throw new EmptyDequeException("Deque is empty.");
        }
        return A[front % capacity];       
    }
    /**
     * Returns the last element of the deque
     */
    public int getLast( ) throws EmptyDequeException
    {  
        if(isEmpty()){
            throw new EmptyDequeException("Deque is empty.");
        }
        return A[(front + rear - 1) % capacity];   // replace this line with your code         
    }
    /**
     * Inserts e at the beginning (as the first element) of the deque
     */
    public void insertFirst( int e )
    {
        rear++;
        if(size() == capacity){
            capacity *= 2;
        }
        int[] B = new int[capacity];
        for(int i = 0; i < size(); i++){
            B[i] = A[i];
        }
        A = B;
        for(int i = size(); i >= front; i--){
            A[i+1] = A[i];
        }
        A[front] = e;
        front = front % capacity;
    }
    /**
     * Inserts e at the end (as the last element) of the deque
     */
    public void insertLast( int e )
    {
        if(size() == capacity){
            capacity *= 2;
            A[rear++] = e;
        }
        else{
            A[rear++] = e;
        }
        rear++;
    }
    /**
     * Removes and returns the first element of the deque
     * Shrink array by half of current size N when number of elements in the deque falls below N/4
     * minimum capacity should always be 8
     */
    public int removeFirst( ) throws EmptyDequeException
    {
        if(size() == 0){
            throw new EmptyDequeException("Deque is empty.");
        }
        if(capacity >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = 1; i < size(); i++){
            B[i-1] = A[i];
        }
        A = B;
        return A[front];
    }
    /**
     * Removes and returns the last element of the deque
     * Shrink array by half of current size N when number of elements in the deque falls below N/4
     * minimum capacity should always be 8
     */
    public int removeLast( ) throws EmptyDequeException
    {
        if(size() == 0){
            throw new EmptyDequeException("Deque is empty.");
        }
        if(capacity >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = front; i<size()-1; i++){
            B[i] = A[i];
        }
        A = B;
        rear--;
        return A[rear];
    }
}  // end class

Answer 1

代码 size() == capacity 永远不会成立，这就是它不扩展的原因。使其size() ==capacity - 1。

我放弃这个是因为它很容易被忽视

Answer 2

根据您给定的代码， front 的值将始终保留值零。

1. 在removeFirst()中，你必须执行front++；
2. 在insertLast()中，你做了两次rear++。您可以删除 if/else 之外的后++。
3. removeFirst() 始终返回第二个元素，因为该方法中的 for 循环会丢失第一个元素。

注意：以上任何一种情况都不会使其成为循环队列。建议：阅读并重新实现:)

Answer 3

我之前在 C 上做了一个实现。我认为应该很容易移植到 Java，或者至少给你一个关于如何在 Java 中实现它的提示。

谢谢，
塞尔吉奥.

类型定义结构{
void *elems; / 数据。 */
尺寸_t 尺寸； /* 队列的容量。 */
size_t 内莱姆斯； /* 队列中的元素数量。 */
首先是size_t； /* 指向队列中的第一个元素。 */
nx_queue_t；

nx_queue_t *nx_queue_create (size_t 大小) {
nx_queue_t *q;

if ( (q = malloc (sizeof(nx_queue_t))) == NULL )
    return (NULL);

q->sz = size;
q->nelems = 0;
q->first=0;

if ( (q->elems = malloc (sizeof(void*)*size)) == NULL ) {
    free (q);
    return (NULL);
}

return (q);

}

size_t nx_queue_capacity (nx_queue_t *q)
{
返回（q->sz）；
}

size_t nx_queue_size (nx_queue_t *q)
{
返回（q-> nelems）；
int

nx_queue_empty (nx_queue_t *q)
{
return (!q->nelems);
int

nx_queue_full (nx_queue_t *q)
{
return (q->nelems == q->sz);
int

nx_queue_enqueue (nx_queue_t *q, void *elem)
{
大小_t i；

if (nx_queue_full (q))
    return (-1);

i = (q->first + q->nelems) % q->sz;
q->elems[i] = elem;
q->nelems++;

}

无效 *nx_queue_dequeue (nx_queue_t *q)
{
无效*元素；

if (nx_queue_empty (q))
    return (NULL);

elem = q->elems[q->first];
q->first = (q->first + 1) % q->sz;
q->nelems--;

return (elem);

}

Answer 4

class Deque{
    int capacity=0,back=-2,front=0;
    int*array=NULL;
    bool isEmpty(){
        return back==-2;
    }
    bool isFull(){
        return ((front-1+capacity)%capacity==back)||((back+1)%capacity==front);
    }
    public:
    Deque(int n){
        capacity=n;
        array= new int[n];
        cout<<"deque allocated with capacity "<<n<<endl;
    }
    ~Deque(){
        delete[] array;
        cout<<"deque deleted\n";
    }
    bool push_back(int x){
        if(isFull())
            return false;
        if(back==-2)
            back=-1;
        back=(back+1)%capacity;
        array[back]=x;
        return true;
    }
    bool push_front(int x){
        if(isFull())
            return false;
        if(back==-2){
            back=0;
            front=1;
        }
        front=(front-1+capacity)%capacity;
        array[front]=x;
        return true;
    }
    int pop_back(){
        if(isEmpty())
            return -1000;
        int a=array[back];
        if(back==front){
            front=0;
            back=-2;
        }
        else
            back=(back-1+capacity)%capacity;
        return a;
    }
    int pop_front(){
        if(isEmpty())
            return -1000;
        int a=array[front];
        if(back==front){
            front=0;
            back=-2;
        }
        else
            front=(front+1)%capacity;
        return a;
    }
    void print(){
        if(isEmpty())
            cout<<"deque is empty\n";
        else{
            int temp=front;
                while(temp!=back){
                    cout<<array[temp]<<" ";
                    temp=(temp+1)%capacity;
                }
            cout<<array[temp]<<endl;
        }
    }
};