Блог

Я некоторое время пытался понять код, приведенный ниже. Это делается для реализации очереди с использованием массива, но без подсчета элементов внутри очереди при вставке и удалении, т. Е. просто с использованием заднего и переднего индексов. Идея заключалась в том, чтобы увеличить размер массива на 1, чтобы условия для «isFull()» и «isEmpty()» не совпадали.

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

 public class QueueWo {

    private int maxSize;
    private long[] arr;
    private int rear;
    private int front;

    public QueueWo(int s) {
        maxSize = s   1;
        arr = new long[maxSize];
        rear = -1;
        front = 0;
    }

    public void insert(long j) {
        if(rear == maxSize - 1)
            rear = -1;
        arr[  rear] = j;
    }

    public long remove() {
        long temp = arr[front  ];
        if(front == maxSize)
            front = 0;
        return temp;
    }

    public long peek() {
        return arr[front];
    }

    public boolean isEmpty() {
        return rear   1 == front || front   maxSize - 1 == rear;
    }

    public boolean isFull() {
        return rear   2 == front || front   maxSize - 2 == rear;
    }

    public int size() {
        if(rear >= front)
            return rear - front   1;
        else
            return (maxSize - front)   (rear   1);
    }
}
 

Вы создаете массив фиксированного размера и начинаете помещать в него элементы. Как только вы достигнете конца, поставив элементы в очередь, вы начнете с начала массива и так далее по кругу. При этом ваш фронт продолжает двигаться на один индекс вперед при каждом удалении и, дойдя до конца, начинает с самого начала.