扩展圆形数组双端队列的问题

Question

您好，

我正在尝试使用循环数组来实现双端队列，该数组在数组满时会扩展。我的问题似乎是数组拒绝扩展。要么是我错误地计算了 size() ，要么是我更新前索引和后索引的方式存在问题。我已经看了很多次了，我似乎明白了这一点。有人可以帮忙吗？

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;
       }

        /**
         * Display the content of the deque
         */
        public void printDeque( )
        {
          for ( int i = front; i != rear; i = (i+1) % capacity )
              System.out.print( A[i] + " " );
              System.out.println();
        }
       /**
         * Returns the number of items in this collection.
         */
        public int size()
        {
            return (capacity - front + rear) % capacity;
        }
        /**
         * Returns 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[(rear - 1) % capacity];        
        }
        /**
         * Inserts e at the beginning (as the first element) of the deque
         * If array is full, extend array by doubling its capacity and insert element in new array
         */
        public void insertFirst(int e)
        {
            if(size() == capacity){
                int[] B = new int[2*capacity];
                for(int i = 0; i < size(); i++){
                    B[i] = A[i];
                }
                A = B;
            }
            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;
            rear = (rear + 1) % capacity;
        }
        /**
         * Inserts e at the end (as the last element) of the deque
         * If array is full, extend array by doubling its capacity and insert element in new array
         */
        public void insertLast(int e)
        {
            if(size() == capacity){
                capacity *= 2;
                int[] B = new int[capacity];
                for(int i = 0; i < size(); i++){
                    B[i] = A[i];
                }
                A = B;
            }
            A[rear] = e;
            rear = (rear + 1) % capacity;
        }
        /**
         * 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(isEmpty()){
                throw new EmptyDequeException("Deque is empty.");
            }
            else if(capacity >= 8){
                if(size() < capacity/4){
                    capacity /= 2;
                    int[] B = new int[capacity];
                    for(int i = 0; i < size(); i++){
                        B[i] = A[i];
                    }
                    A = B;
                }
            }
            int temp = A[front];
            A[front] = 0;
            front = (front + 1) % capacity;
            return temp;
        }
        /**
         * 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(isEmpty()){
                throw new EmptyDequeException("Deque is empty.");
            }
            else if(capacity >= 8){
                if(size() < capacity/4){
                    int[] B = new int[capacity/2];
                    for(int i = 0; i < capacity; i++){
                        B[i] = A[i];
                    }
                    A = B;
                }
            }
            int temp = A[rear - 1];
            A[rear] = 0;
            rear = (rear - 1) % capacity;
            return temp;
        }
    }  // end class

测试输入：

for(i = 1; i <= 100; i++)
   q.insertLast(i);
   q.printDeque();

for(i = 1; i <= 99; i++)
   k = q.removeFirst();
   q.printDeque();

测试输出： 我已经设置了几个打印语句，但出于某种原因，大小始终保持在 7...

Exception in thread "main" A3.EmptyDequeException: Deque is empty.
    at A3.ArrayDeque.removeFirst(ArrayDeque.java:133)
    at A3.ArrayMain.main(ArrayMain.java:37)

Answer 1

好吧，考虑一下...

如果您的最大容量是 8，那么您的队列可以有 9 个总大小状态：0 1 2 3 4 5 6 7 和 8。

ANY_NUMBER % 8 只能有 8 个状态：0 1 2 3 4 5 6 和 7。

这是家庭作业（感谢您诚实地对待它），所以我不想破坏这一切，但这应该为您指明正确的方向。祝你好运！

Answer 2

看看你的 insertFirst 方法，当数组已满时它会做什么。阅读整个方法，而不仅仅是第一个 if 块。你有改变你的能力吗？