26. Приведите пример реализации Dequeue.

ArrayDeque (также известный как «Array Double Ended Queue», произносится как «ArrayDeck») - это особый вид растущего массива, который позволяет нам добавлять или удалять элементы с обеих сторон.

Реализация ArrayDeque может использоваться как Stack (последний пришел-первый вышел) или Queue (первый пришел-первый вышел)

Под капотом ArrayDeque поддерживается массив, который удваивает свой размер при заполнении.

Первоначально, массив инициализируется с размером 16. Он реализован как двусторонняя очередь, где он поддерживает два указателя, а именно голову и хвост.

ArrayDeque:

• Это не потокобезопасный
• Нулевые элементы не принимаются
• Работает значительно быстрее, чем синхронизированный Stack
• Более быстрая очередь, чем LinkedList из-за лучшей локализации. Большинство операций амортизировали сложность с постоянным временем
• Iterator , возвращаемый ArrayDeque , является отказоустойчивым
• ArrayDeque автоматически удваивает размер массива, когда head и хвостовой указатель встречает друг друга при добавлении элемента

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);

stack.push(2);

stack.push(3);

while (!stack.isEmpty()) {

System.out.println(stack.pop());

}

Результат:

3

2

1

Выводы

На основании рассмотренных нами интерфейсов и реализаций можно сделать вывод, что для самой простой реализации очереди Queue следует выбрать LinkedList. Eсли требуется как-то сортировать элементы внутри очереди, то подойдёт PriorityQueue. Если же нам нужна функциональность стека, то надо использовать интерфейс Deque и одну из его реализаций: LinkedList или ArrayDeque

Предыдущий вопрос: 25. Что такое Dequeue? Чем отличается от Queue?

Следующий вопрос: 27. Какая коллекция реализует FIFO? Queue

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне