круговая очередь: значения массива исчезают при удвоении размера

Question

В моей реализации циклической очереди есть проблема, когда я удваиваю размер массива в методе resize ().Некоторые значения исчезают.

Я считаю, что метод dequeue () не имеет к этому никакого отношения.Я подозреваю, что что-то не так с методом enqueue () или методами печати.Я проверил в Интернете некоторые ответы, но не смог их найтиБудем признательны за помощь, поскольку я не могу найти проблему

CircularArrayQueue.java

public class CircularArrayQueue {
    private final int CAPACITY = 10;
    private int[] data;         
    private int front = 0;      
    private int size = 0;       


    public CircularArrayQueue() {
        data = new int[CAPACITY];
    }

    public CircularArrayQueue(int capacity) {
        data = new int[capacity];
    }

    public void enqueue(int element) {
        if (size == data.length) {
            resize();
        }
        data[(front + size) % data.length] = element;
        size++;
    }

    public void resize() {
        int[] temp = data;
        int currentLength = data.length;
        data = new int[2*currentLength];
        System.arraycopy(temp, 0, data, 0, currentLength);
    }

    public int dequeue() {
        if (size == 0) 
            return Integer.MIN_VALUE;

        int temp = data[front];
        data[front] = 0;
        front = (front + 1) % data.length;
        size--;
        return temp;
    }

    public int peek() {
        if (size == 0) 
            return Integer.MIN_VALUE;

        return data[front];
    }

    public int getSize() {
        return size;
    }

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

    public void printQueue() {
        if(size == 0) {
            System.out.println("Queue is EMPTY!");
        }else {
            System.out.print("Queue: ");
            for(int i = 0; i < size; i++) {
                System.out.print(data[(i+front)%data.length]+" ");
            }
            System.out.println("");
        }
    }

    public void printArray() {
        System.out.print("Array: ");
        for(int i : data) {
            System.out.print(i+" ");
        }
        System.out.println("");
    }
}

MainCircularArrayQueue.java

public class MainCircularArrayQueue {

    public static void main(String[] args) {
        CircularArrayQueue queue = new CircularArrayQueue(3);
        System.out.println("Add 3 elements");
        queue.enqueue(11);
        queue.enqueue(22);
        queue.enqueue(33);
        queue.printQueue();
        queue.printArray();
        System.out.println();

        System.out.println("Remove 1 element");
        System.out.println("Remove: " + queue.dequeue());
        queue.printQueue();
        queue.printArray();
        System.out.println();

        System.out.println("Add 1 more element");
        queue.enqueue(44);
        queue.printQueue();
        queue.printArray();
        System.out.println();

        System.out.println("Add 1 more element");
        queue.enqueue(55);
        queue.printQueue();
        queue.printArray();
        System.out.println();

        System.out.println("Remove 1 element");
        System.out.println("Remove: " + queue.dequeue());
        queue.printQueue();
        queue.printArray();
        System.out.println();

        System.out.println("Add 4 more elements");
        queue.enqueue(66);
        queue.enqueue(77);
        queue.enqueue(88);
        queue.enqueue(99);
        queue.printQueue();
        queue.printArray();
    }
}

Ожидаемые результаты

Add 3 elements
Queue: 11 22 33 
Array: 11 22 33 

Remove 1 element
Remove: 11
Queue: 22 33 
Array: 0 22 33 

Add 1 more element
Queue: 22 33 44 
Array: 44 22 33 

Add 1 more element
Queue: 22 33 44 55 
Array: 22 33 44 55 0 0 

Remove 1 element
Remove: 22
Queue: 33 44 55 
Array: 0 33 44 55 0 0 

Add 4 more elements
Queue: 33 44 55 66 77 88 99 
Array: 33 44 55 66 77 88 99 0 0 0 0 0 

Фактический результат:

Add 3 elements
Queue: 11 22 33
Array: 11 22 33

Remove 1 element
Remove: 11
Queue: 22 33
Array: 0 22 33

Add 1 more element
Queue: 22 33 44
Array: 44 22 33

Add 1 more element
Queue: 22 33 0 55
Array: 44 22 33 0 55 0

Remove 1 element
Remove: 22
Queue: 33 0 55
Array: 44 0 33 0 55 0

Add 4 more elements
Queue: 33 0 55 66 0 0 99
Array: 77 88 33 0 55 66 0 0 99 0 0 0

Answer 1

Проблема не обязательно с enqueue() или dequeue().Происходит следующее: когда размер буфера автоматически изменяется, он меняет порядок элементов в очереди.Когда массив равен [44 22 33], front имеет индекс 1, а "задняя позиция" определяется как индекс size перед ним, также оборачиваясь вокруг индекса 1.Добавление следующего числа вызывает изменение размера массива, образуя [44 22 33 0 0 0].55 добавляется в индексе 4, потому что вычисление «задней позиции» больше не переносится вокруг конца массива.Приведенный выше пример кода Мокаррома Хоссейна должен работать, потому что он изменил resize(), чтобы скопировать числа из исходного массива в массив с измененным размером в том порядке, в котором они были поставлены в очередь.

Answer 2

Вам также необходимо отслеживать rear.

class CircularArrayQueue {
    private final int CAPACITY = 10;
    private int[] data;         
    private int front = 0;   
    private int rear = 0;
    private int size = 0;       


    public CircularArrayQueue() {
        data = new int[CAPACITY];
    }

    public CircularArrayQueue(int capacity) {
        data = new int[capacity];
    }

    public void enqueue(int element) {
        if (size == data.length) {
            resize();
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    public void resize() {
        int[] temp = data;
        int currentLength = data.length;
        data = new int[2*currentLength];

        for (int i = 0; i < currentLength; i++) {
            data[i] = temp[(i + front) % currentLength];
        }

        front = 0;
        rear = currentLength;
    }

    public int dequeue() {
        if (size == 0) 
            return Integer.MIN_VALUE;

        int temp = data[front];
        data[front] = 0;
        front = (front + 1) % data.length;
        size--;
        return temp;
    }

    public int peek() {
        if (size == 0) 
            return Integer.MIN_VALUE;

        return data[front];
    }

    public int getSize() {
        return size;
    }

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

    public void printQueue() {
        if(size == 0) {
            System.out.println("Queue is EMPTY!");
        }else {
            System.out.print("Queue: ");
            for(int i = 0; i < size; i++) {
                System.out.print(data[(i+front)%data.length]+" ");
            }
            System.out.println("");
        }
    }

    public void printArray() {
        System.out.print("Array: ");
        for(int i : data) {
            System.out.print(i+" ");
        }
        System.out.println("");
    }
}