Почему очередь на основе массива не работает должным образом?

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

Для постановки в очередь ваш код должен понравиться.в вашем коде есть проблема, когда вы увеличиваете размер до.

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

    }

и для удаления из очереди вы не должны выполнять операции на основе Popped каждый раз, когда вам нужно удалить 0 index .

    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() операцию, вы всегда должны remove an element at index 0.Так ты no need increment popped.It should be always 0 (index 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

    }