Очередь реализуется с помощью круговой массив


Я нашел учебник о реализации очереди с помощью круговой массив. Я изменил реализации, но я не уверен, если это правильно или нет.

Так у меня один вопрос:

  1. Я написал код, который использует addCount поле для записи, есть ли какие-то дополнения, но я не уверен, если это правильно? Если нет, пожалуйста, скажи мне, где я допустил ошибку.

class Deque {
    static final int MAX = 100;
    int arr[];
    int front;
    int rear;
    int size;
    int addCount;

    public Deque(int size) {
        arr = new int[size];
        front = 0;
        rear = 0;
        this.size = size;
        addCount = 0;
    }

    // Checks whether Deque is full or not.
    boolean isFull() {

        return front == rear && !isEmpty();
    }

    // Checks whether Deque is empty or not.
    boolean isEmpty() {
        return front == rear && addCount == 0;
    }

    // Inserts an element at front
    void insertfront(int key) {
        if (isFull())
            return;

        addCount++;
        arr[front] = key;
        front = front + 1;
        front %= this.size;
    }

    // function to inset element at rear end
    // of Deque.
    void insertrear(int key) {
        if (isFull())
            return;
        addCount++;
        rear = (rear - 1) % this.size;
        arr[rear + this.size] = key;

    }

    // Deletes element at front end of Deque
    void deletefront() {
        if (isEmpty())
            return;
        addCount--;
        front = (front - 1) % this.size;
    }

    // Delete element at rear end of Deque
    void deleterear() {
        if (isEmpty())
            return;
        addCount--;
        rear = (rear + 1) % this.size;
    }

    // Returns front element of Deque
    int getFront() {
        int getFront = front-1;

        if (getFront < 0)
            getFront += this.size;
        return arr[getFront % this.size];
    }

    // function return rear element of Deque
    int getRear() {
        int getRearIndex = rear + this.size;
        return arr[getRearIndex % this.size];
    }

    // Driver program to test above function
    public static void main(String[] args) {
        Deque dq = new Deque(5);
        System.out.println("Insert element at rear end : 5 ");
        dq.insertrear(5);

        System.out.println("insert element at rear end : 10 ");
        dq.insertrear(10);

        System.out.println("get rear element : " + dq.getRear());

        dq.deleterear();
        System.out.println("After delete rear element new rear become : " + dq.getRear());

        System.out.println("inserting element at front end");
        dq.insertfront(15);

        System.out.println("get front element: " + dq.getFront());

        dq.deletefront();

        System.out.println("After delete front element new front become : " + +dq.getFront());

    }
}


1156
1
задан 7 февраля 2018 в 02:02 Источник Поделиться
Комментарии
3 ответа

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

Представленные решения-это коллекция, которая может принимать только int элементы. Вы можете расширить это, если вы добавляете параметр универсального класса. Обратите внимание, что в этом случае внутренний массив из Object[] типа и компилятор обеспечить безопасность типов, а также сделать авто-бокса, чтобы поддержать примитивные данные элементы, как и в Java библиотечных фондов. И пока мы упомянули, что вы, возможно, захотите рассмотреть вопрос о внесении вашего решения осуществить Deque интерфейс в Java коллекции, так что клиенты будут работать с привычным API-интерфейс (конечно, вы хотите, чтобы изменить имя класса, которое отражает его конкретную реализацию Deque)

2
ответ дан 7 февраля 2018 в 09:02 Источник Поделиться

Ошибки

Если вы называете insertrear() и deletefront() неоднократно, вы в итоге получите массив вне границ исключение. Есть как минимум две проблемы:

Этот код в insertrear() может индексировать мимо конца массива:


    rear = (rear - 1) % this.size;
arr[rear + this.size] = key;

Если первое утверждение результатов rear быть 0, второе заявление будет пытаться получить доступ к элементу вне границ.

Этот код в deletefront() может вызвать front чтобы стать отрицательным:


    front = (front - 1) % this.size;

что приведет к следующим addfront() звоните, чтобы бросить исключение, потому что он будет пытаться использовать front в качестве индекса массива без фиксации.

Я бы порекомендовал не давая front и rear идут отрицательные. Во-первых, это устраняет границы массива вопросов. Во-вторых, это также устраняет дополнительные ошибка при проверке front == rear и он должен возвращать значение true, но это не потому, что один показатель положительный и один отрицательный показатель.

Бедный испытание

Если вы осуществили ваш код, вы могли бы заняться эти ошибки. При написании тестов для вашего кода, Вы должны убедиться, чтобы подчеркнуть его, а не просто сделать абсолютный минимум. Например, вы должны заполнить свой очереди в емкость и посмотреть, что произойдет, если попытаться перенасытить. Вы должны попробовать каждую комбинацию наполнения спереди/сзади с удалением от переднего/заднего (4 отдельные испытания, по крайней мере).

1
ответ дан 7 февраля 2018 в 09:02 Источник Поделиться

С кольцевой буфер, вам нужно только отслеживать две переменные: writeIndex и itemCount.


  • Оба элемента увеличивается, когда вы написать пункт в буфер

  • itemCount уменьшается, когда вы читаете элемента из буфера

  • Вам рассчитают читать индекс путем вычитания itemCount от writeIndex

  • Переход от нижней части буфера к вершине, используя модуль математика

Вот подробности:

Добавить данные в буфер:

writeIndex = ((writeIndex + 1) % BUFFER_SIZE)
if (itemCount < BUFFER_SIZE) itemCount++;
write data to buffer[writeIndex]

Удалить данные из буфера:

if (itemCount > 0) 
readIndex = ((BUFFER_SIZE + writeIndex - itemCount + 1) % BUFFER_SIZE)
read data from the buffer[readIndex]
itemCount--;
}

Пример:

BUFFER_SIZE = 6
writeIndex = 4
itemCount = 3

add item, new writeIndex = (4 + 1) % 6 = 5 % 6 = 5 new itemCount = 4
add item, new writeIndex = (5 + 1) % 6 = 6 % 6 = 0 new itemCount = 5
read item, new readIndex = (6+0-5+1) % 6 = 2%6 = 2 new itemCount = 4
read item, new readIndex = (6+0-4+1) % 6 = 3%6 = 3 new itemCount = 3


  • % = сл ... возвращает остаток от деления

  • 5%6 = 5/6, остаток 5

  • 6%6 = 6/6, остаток 0

Этот пример разрешает перезапись непрочитанных данных.

Перезапись может быть отключена:

if (itemCount<BUFFER_SIZE) { write logic}

Этот пример не является потокобезопасным. Если вы читать и писать на разные темы, вам необходимо добавить механизм блокировки для обеспечения чтения и записи операции не происходят одновременно.

0
ответ дан 12 февраля 2018 в 01:02 Источник Поделиться