Java for Beginner

ArrayDeque, внутреннее устройство, особенности и преимущества

ArrayDeque — это реализация двусторонней очереди (deque) на основе массивов, предоставляемая в пакете java.util. Она представляет собой гибкую структуру данных, которая поддерживает вставку и удаление элементов с обеих сторон с амортизированным постоянным временем.

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }
    }
}

В этом примере элементы вставляются и извлекаются с обеих сторон очереди, демонстрируя гибкость ArrayDeque.

Внутреннее устройство ArrayDeque

ArrayDeque основана на циклическом массиве, который расширяется по мере необходимости. Это позволяет поддерживать эффективное использование памяти и быструю вставку и удаление элементов с обеих сторон очереди.

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
    private transient E[] elements;
    private transient int head;
    private transient int tail;

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

    public ArrayDeque(int initialCapacity) {
        elements = (E[]) new Object[initialCapacity];
    }

    // Основные методы: addFirst, addLast, pollFirst, pollLast, etc.
}

Особенности и преимущества

Циклический массив: Использование циклического массива позволяет избежать необходимости перемещения элементов при вставке и удалении с обеих сторон.
Амортизированное постоянное время: Вставка и удаление элементов с обеих сторон выполняются в амортизированное постоянное время O(1), за исключением случаев расширения массива.
Отсутствие блокировок: ArrayDeque не синхронизирована, что делает её быстрее по сравнению с синхронизированными структурами данных, такими как LinkedBlockingDeque.
Гибкость: Поддержка операций вставки и удаления с обеих сторон очереди предоставляет большую гибкость в использовании.

Преимущества использования ArrayDeque

Производительность: ArrayDeque обеспечивает более высокую производительность по сравнению с LinkedList для операций вставки и удаления элементов с обеих сторон.
Гибкость: Она поддерживает как стековые (push, pop), так и очередные (offer, poll) операции, что делает её универсальной для различных задач.
Эффективное использование памяти: Благодаря циклическому массиву ArrayDeque эффективно использует память, минимизируя количество операций по перемещению элементов.

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        // Добавление элементов
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        // Извлечение элементов
        System.out.println(deque.pollFirst()); // 3
        System.out.println(deque.pollLast());  // 4
        System.out.println(deque.pollFirst()); // 1
        System.out.println(deque.pollLast());  // 2
    }
}

В этом примере демонстрируются основные операции вставки и извлечения элементов с обеих сторон очереди.

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-array-deque
https://metanit.com/java/tutorial/5.7.php

#Java #Training #Medium #ArrayDeque

Baeldung

Introduction to the Java ArrayDeque | Baeldung

A quick and practical introduction to ArrayDeque in Java.

224 viewsДен, 05:34

Java for Beginner

Основные методы ArrayDeque и их применение

Основные методы ArrayDeque:

addFirst(E e):
Добавляет элемент в начало очереди. Если очередь заполнена, увеличивает её размер.

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(10);
deque.addFirst(20);
System.out.println(deque); // [20, 10]

addLast(E e):
Добавляет элемент в конец очереди. Если очередь заполнена, увеличивает её размер.

deque.addLast(30);
System.out.println(deque); // [20, 10, 30]

offerFirst(E e):
Предлагает добавить элемент в начало очереди. Возвращает true, если элемент был добавлен успешно.

deque.offerFirst(40);
System.out.println(deque); // [40, 20, 10, 30]

offerLast(E e):
Предлагает добавить элемент в конец очереди. Возвращает true, если элемент был добавлен успешно.

deque.offerLast(50);
System.out.println(deque); // [40, 20, 10, 30, 50]

pollFirst():
Возвращает и удаляет первый элемент из очереди. Возвращает null, если очередь пуста.

Integer first = deque.pollFirst();
System.out.println(first); // 40
System.out.println(deque); // [20, 10, 30, 50]

pollLast():
Возвращает и удаляет последний элемент из очереди. Возвращает null, если очередь пуста.

Integer last = deque.pollLast();
System.out.println(last); // 50
System.out.println(deque); // [20, 10, 30]

peekFirst():
Возвращает первый элемент из очереди, не удаляя его. Возвращает null, если очередь пуста.

Integer peekFirst = deque.peekFirst();
System.out.println(peekFirst); // 20

peekLast():
Возвращает последний элемент из очереди, не удаляя его. Возвращает null, если очередь пуста.

Integer peekLast = deque.peekLast();
System.out.println(peekLast); // 30

push(E e):
Вставляет элемент на вершину стека. Эквивалентен методу addFirst(E e).

deque.push(60);
System.out.println(deque); // [60, 20, 10, 30]

pop():
Возвращает и удаляет элемент с вершины стека. Эквивалентен методу pollFirst().

Integer pop = deque.pop();
System.out.println(pop); // 60
System.out.println(deque); // [20, 10, 30]

Примеры использования ArrayDeque

Реализация стека с использованием ArrayDeque:

import java.util.ArrayDeque;

public class StackExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Реализация очереди с использованием ArrayDeque:

import java.util.ArrayDeque;

public class QueueExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        queue.addLast(1);
        queue.addLast(2);
        queue.addLast(3);

        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
    }
}

Реализация двусторонней очереди с использованием ArrayDeque:

import java.util.ArrayDeque;

public class DequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }
    }
}

#Java #Training #Medium #ArrayDeque

237 viewsДен, 14:14

About

Blog

Apps

Platform