为什么基于数组的队列不能正常工作？

Question

我已经为基于数组的队列编写了一个代码。它的行为非常奇怪，就像我使用for循环将0,1,2,3,4排队一样，但是插入队列的是0,0,1,2,3。

另外，出列时会抛出ArrayOutOfBoundsException，我不知道为什么。

我使用的排队逻辑是，我把元素放在一个简单的数组中。额外的一点是，如果大小接近容量的一半，我会增加数组的容量。

对于出列，如果大小小于容量的三分之一，我将减小容量。我还为popped保留了一个计数器，它从数组的开头弹出元素。

以下是我使用过的代码：

class ArrayQueue {

      private int[] arr;
      private int size;
      private int capacity;
      private int popped = 0;

      public ArrayQueue(int capacity) {

        this.capacity = capacity;
        size = 0;
        arr = new int[capacity];
      }

      public int size() {
        return size;
      }

      public int capacity() {
        return capacity;
      }

      public void enqueue(int ele) {

        size++;

        if(size >= capacity/2) {

            capacity = capacity*2;

            int[] nArr = new int[capacity];

            for(int i=0;i<size;i++)
                nArr[i] = arr[i];

            arr = nArr;

        }

        arr[size] = ele;

      }

      public void dequeue() {

        size--;

        System.out.println(arr[popped]+" removed");

        if(size <= capacity/3) {

            capacity = capacity/2;

            int[] nArr = new int[capacity];

            for(int i=0;i<size;i++)
                nArr[i] = arr[i];

            arr = nArr;

        }

        int[] nArr = new int[capacity];

        for(int i=0;i<popped;i++)
            nArr[i] = arr[i];

        for(int i=popped+1;i<size;i++)
            nArr[i-1] = arr[i];

        arr = nArr;

        popped++;

    }

    public boolean isEmpty() {
        return (size == 0);
    }

    public void showQueue() {

        for(int i=0;i<size;i++)
            System.out.println("| "+arr[i]+" |");

    }
    }



    public static void main(String[] args) {

        ArrayQueue a = new ArrayQueue(10);

        System.out.println("Starting size "+a.size());

        for(int i=0;i<5;i++) {

            a.enqueue(i);
            System.out.println("Current size is "+a.size());
            System.out.println("Current capacity is "+a.capacity());

        }

        System.out.println();

        a.showQueue();

        System.out.println();

        a.dequeue();

        System.out.println("Size: "+a.size());
        System.out.println("Current capacity is "+a.capacity());

        a.dequeue();

        System.out.println("Size: "+a.size());
        System.out.println("Current capacity is "+a.capacity());

        a.dequeue();

        System.out.println("Size: "+a.size());
        System.out.println("Current capacity is "+a.capacity());

        a.dequeue();

        System.out.println("Size: "+a.size());
        System.out.println("Current capacity is "+a.capacity());


    }

我得到的结果是：

Starting size 0
Current size is 1
Current capacity is 10
Current size is 2
Current capacity is 10
Current size is 3
Current capacity is 10
Current size is 4
Current capacity is 10
Current size is 5
Current capacity is 20

| 0 |
| 0 |
| 1 |
| 2 |
| 3 |

0 removed
Size: 4
Current capacity is 10
1 removed
Size: 3
Current capacity is 5
0 removed
Size: 2
Current capacity is 5
0 removed
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at ArrayQueue.dequeue(Code.java:228)
    at Code.main(Code.java:76)

Answer 1

对于enqueue，您的代码应该如下所示。在您的代码中，当您之前增加大小时，它会出现问题。

public void enqueue(int ele) {



      if(size >= capacity/2) {

          capacity = capacity*2;

          int[] nArr = new int[capacity];

          for(int i=0;i<size;i++)
              nArr[i] = arr[i];

          arr = nArr;

      }

      arr[size] = ele;
      size++;

    }

对于出列，您不应该在每次需要删除0索引时基于Popped执行操作。

    public void dequeue() {

    System.out.println(arr[0] + " removed");
    if (size <= capacity / 3) {
        capacity = capacity / 2;
        int[] nArr = new int[capacity];
        for (int i = 0; i < size; i++)
            nArr[i] = arr[i];
        arr = nArr;
    }

    int[] nArr = new int[capacity];

    for (int i = 1; i < size; i++) // every time we need to pop first index
        nArr[i - 1] = arr[i];

    arr = nArr;

    popped++;
    size--;

}

Answer 2

执行deQueue（）操作时，应始终删除索引0处的元素。所以你不需要增量弹出。它应该总是0（索引0）

    public void dequeue() {

        size--;

        System.out.println(arr[popped] + " removed");

        if (size <= capacity / 3) {

            capacity = capacity / 2;

            int[] nArr = new int[capacity];

            for (int i = 0; i < size; i++)
                nArr[i] = arr[i];

            arr = nArr;

        }

        int[] nArr = new int[capacity];

/*      for (int i = 0; i < popped; i++)
            nArr[i] = arr[i]; //Not required as popped is always 0
*/
        for (int i = popped + 1; i < size; i++)
            nArr[i - 1] = arr[i];

        arr = nArr;

        //popped++; // not required as we remove first element

    }