[Анализ исходного кода] Вы действительно понимаете ArrayDeque?

Накопите тысячи миль и соберите тысячи миль рек; делайте понемногу каждый день, и однажды вы станете боссом

предисловие

В предыдущей статье было сказаноLinkedListтакже может быть достигнуто队列а также栈функция, но если мы обычно используем функцию очереди, рекомендуется использоватьArrayDeque, потому что его нижний слоймножество, в то время как очереди и стеки имеют длинуМанипулировать головой или хвостом, поэтому производительность массива немного выше, чем у связанного списка.

LinkedListа такжеArrayDequeдостигаются за счетDequeэтот интерфейс, чтобы получить队列а также栈функция. а такжеDequeЭтот интерфейс наследуетсяQueueЭтот интерфейс используется для получения функции очереди, а затем расширяется на этой основе для достижения双端队列, чтобы можно было получить栈функция. Чтобы максимально использовать пространство,ArrayDequeиспользовал循环队列;а такжеLinkedListможно вставитьnullзначение, в то время какArrayDequeне может быть вставленnullиз.

Что такое дека?

Короче говоря, это очередь, с которой можно работать на обоих концах (🌚 сказано и не сказано одно и то же...). Ха-ха, давайте посмотрим на картинку

Общая очередь такая:

Двусторонняя очередь выглядит так

Как правило, обычные очереди могут удалять элементы только в начале и добавлять элементы в конце, в то время как очереди могут добавлять и удалять элементы в начале и в конце.

Что такое круговая очередь?

Лучше сказать, что вы задали массив емкостью 5. Позиция, которую вы вставляете в первый раз, это индекс 2. Когда вы добавляете 4-й элемент, он не расширяется, а проходитуказатель головы и хвостаСделайте сравнение, а затем вставьте данные в позицию с нижним индексом 0. когдаКогда указатели головы и хвоста равны, указывая на то, что массив очереди заполнен, и он будет расширен только в это время.

Порядок массива здесь сверху вниз.Некоторые люди спросят, почему все указатели головы и хвоста указывают на третий квадрат? Потому что демонстрация здесь заключается в том, что первый элемент вставляется в позицию с нижним индексом 2. . Конечно,ArrayDequeОн начинается с 0, поэтому все указатели начала и конца указывают на позицию с нижним индексом 0 во время инициализации.

Что есть у Дека?

Не мудрствуя лукаво, посмотрите на картинку:

ArrayDequeКонкретный метод реализации в основном находится в синем поле, а два других цветных поля реализуются путем вызова этих методов в синем поле для достижения связанных функций.Вы можете посмотреть на другую карту мозга, которую я нарисовал:

Каждая функция очереди здесь имеет два метода, среди которыхadd(),remove(),element()Если операция не удаласьсообщить об исключении,offer(),poll(),peek()Операция не удаласьвернуть ноль или ложь

На самом деле, реальное использованиетемно-красная коробкаЭти методы написаны на , поэтому я расскажу об этих четырех методах в этой статье,addLast(),pollFirst,getFirst(),addFirst(),peekFirst;

внутренняя переменная

Внутри ArrayDeque всего 4 переменные,элемент массива объектов[],указатель,хвостовой указатель,MIN_INITIAL_CAPACITY указывает, что минимальная емкость инициализации равна 8

Метод строительства

Метод построения такой же, как и у других коллекций, естьпараметризованная конструкцияа такжеКонструктор без аргументов

Конструктор без аргументов

Очень просто, напрямую инициализируйтевместимость 16массив объектов

public ArrayDeque() {
    elements = new Object[16];
}

параметризованная конструкция

Входящий параметр является int

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

• allocateElements(int numElements)Выделите пустой массив для хранения заданного количества элементов.

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

• calculateSize(int numElements)Отрегулируйте размер входящего значения

Алгоритм выше использует битовые операции.Если вы не понимаете битовые операции, вы можете увидетьбитовая операцияЭта статья. Здесь значение устанавливается в n-й степени 2 (целое число), чтобы соответствовать следующим требованиям.循环队列этот алгоритм

Входящий параметр является объектом коллекции

public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

Первый шаг вызывает тот же метод, что и выше, вот еще одинaddAll()метод

• addAll(Collection c)

Не работает при копировании сюда иArrayListтоже самоеSystem.arraycopy()метод, но с использованиемfor循环звонитьadd()Методы добавляются один за другим, зачем это делать? потому чтоArrayDequeВ отличие от других коллекций, он не может содержатьnullзначение, и некоторые другие коллекции могут быть переданыnull, так что здесь мы используемadd()по одному,add()Если переданное значение пусто, методсообщить об исключении; (add() на самом деле вызывает addLast(), что будет обсуждаться ниже)

addLast()

Анализ исходного кода

Смысл этого метода в добавлении данных в хвост.Алгоритм битового И на картинке ниже реализует функцию циклической очереди.основной алгоритм

Помните, что во время инициализации выше, независимо от того, какое значение передается, окончательный вывод2n(целое) квадрат. Этот алгоритмкогда&правильно2n−1час,&Когда число слева является положительным целым числом, независимо от того, насколько оно велико, окончательный результат всегда 2n;когда&Когда число слева равно 0, результат равен 0; когда&Когда число слева отрицательное, -1=2n−1

Приведу несколько примеров: когда2n=8,2n−1=7

• 4&7=4 9&7=1 22&7=6
• 0&7=0
• -1&7=7 -2&7=6 -8&7=0

• doubleCapacity()расширить до исходного2 раза

блок-схема

Для удобства понимания рисую блок-схему верхнего расширения, например, голова находится посередине:

pollFirst()

удалить данные заголовка

Анализ исходного кода

При удалении не похожеArrayListто же, что перемещение данных, но только перемещениеheadуказать на место

блок-схема

getFirst() и peekFirst()

Оба метода одинаковы, оба возвращают напрямуюheadДанные указали, разница в том, что один вызовет исключение, а другой нет.

Анализ исходного кода

• getFirst()

public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

• peekFirst()

public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

addFirst()

Анализ исходного кода

Здесь мы по-прежнему используем алгоритм битового И, упомянутый выше, для вычисленияheadзначение, затем вставьте данные

блок-схема

clear()

Анализ исходного кода

Очистить эту операцию отheadУказанный элемент начинает удаляться до тех пор, покаhead=tail, опорожнение завершено;

size()

Размер этой очереди сбора данных также использует упомянутый выше алгоритм битового И, вычитая начало из хвоста, а затем длину массива битового И -1. Почему ты делаешь это? прямо кArrayListа такжеLinkedListРазве не хорошо определить один и тот же размер?Вам не кажется, что это удобнее? На одну переменную меньше, на одну переменную меньше, и на одну угрозу безопасности меньше.

public int size() {
    return (tail - head) & (elements.length - 1);
}

Суммировать

Вышеупомянутый метод в основном имеет位与На рисунке этого алгоритма видно, что это ядро, если вы не понимаете битовые операции, то можете посмотретьбитовая операцияЭта статья;

Основной алгоритм:

когда&правильно2n−1час,&Когда число слева является положительным целым числом, независимо от того, насколько оно велико, окончательный результат всегда 2n;когда&Когда число слева равно 0, результат равен 0; когда&Когда число слева отрицательное, -1=2n−1

ArrayDequeМетод построения без параметров заключается в прямой инициализации пустого массива емкостью 16, и предыдущая статьяArrayListВ статье его конструктор без аргументов должен инициализироватьпустой массив, емкость увеличивается до 10 только при первом добавлении данных;

ArrayDequeКаждый раз, когда он расширяется до исходной длины массива2 раза

ArrayDequeне может быть вставленnullценность