Черги та клас ArrayDeque. Клас LinkedList

У Java черги — це структури даних, які слідують принципу **FIFO** (First In, First Out — перший увійшов, перший вийшов). Для роботи з чергами використовуються різні класи та інтерфейси, серед яких **`ArrayDeque`** і **`LinkedList`** є популярними реалізаціями.

1. Черги в Java

Черга — це структура даних, яка працює за принципом черги: перший елемент, який додається, першим і вилучається. В Java для реалізації черг використовується інтерфейс Queue, який входить до складу Java Collections Framework.

Основні методи інтерфейсу Queue:

• add(E e): додає елемент в кінець черги.
• remove(): видаляє елемент з початку черги та повертає його.
• peek(): повертає елемент з початку черги без його видалення.
• poll(): повертає та видаляє елемент з початку черги. Якщо черга порожня, повертає null.

2. Клас ArrayDeque

ArrayDeque (Array Double-Ended Queue) — це клас, який реалізує інтерфейси Deque і Queue. Черга з подвійним кінцем дозволяє додавати і видаляти елементи як з початку, так і з кінця черги. Це робить `ArrayDeque` більш гнучкою структурою в порівнянні зі звичайною чергою.

Основні особливості ArrayDeque:

• Вона базується на динамічному масиві.
• ArrayDeque не має обмеження розміру, тобто вона може автоматично змінювати свій розмір під час додавання елементів.
• Швидка реалізація для черг, оскільки вона не використовує синхронізацію (як Vector).

Основні методи ArrayDeque:

• addFirst(E e) і addLast(E e): додають елементи на початок або кінець черги відповідно.
• removeFirst() і removeLast(): видаляють елементи з початку або кінця черги.
• peekFirst() і peekLast(): повертають перший або останній елемент черги без його видалення.

Приклад використання ArrayDeque:

import java.util.ArrayDeque;

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

// Додавання елементів в чергу
deque.addFirst(“Київ”);
deque.addLast(“Львів”);
deque.addLast(“Одеса”);

// Отримання першого і останнього елемента
System.out.println(deque.peekFirst()); // Виведе “Київ”
System.out.println(deque.peekLast()); // Виведе “Одеса”

// Видалення елементів з черги
System.out.println(deque.removeFirst()); // Виведе “Київ”
System.out.println(deque.removeLast()); // Виведе “Одеса”
}
}

Переваги ArrayDeque:

• Швидкість: Додавання і видалення з початку і кінця черги виконується за час O(1).
• Гнучкість: Може бути використана як стек (LIFO — останній увійшов, перший вийшов) або черга (FIFO).
• Відсутність обмежень: Немає фіксованого розміру, що дозволяє використовувати ArrayDeque для динамічних задач.

Недоліки:

• Не дозволяє зберігати null значення. Це обмеження, яке відрізняє ArrayDeque від інших колекцій, таких як LinkedList.

3. Клас LinkedList

LinkedList — це реалізація інтерфейсу List і Deque, яка базується на двозв’язному списку (дво-напрямленій зв’язній структурі). Кожен елемент LinkedList має посилання на попередній і наступний елементи. Це робить LinkedList ефективним для операцій вставки та видалення, особливо в середині списку.

Особливості LinkedList:

• Він може використовуватися як список (List) або черга (Queue), а також як стек (Stack).
• Вставка і видалення елементів є швидкими (O(1)), якщо ви додаєте або видаляєте елементи на початку або кінці списку.
• На відміну від ArrayDeque, LinkedList дозволяє зберігати null значення.

Основні методи LinkedList:

• add(E e): додає елемент у кінець списку.
• addFirst(E e) і addLast(E e): додають елемент на початок або кінець списку.
• remove(), removeFirst(), removeLast(): видаляють перший або останній елемент зі списку.
• get(int index): повертає елемент за індексом (як у масиві).

Приклад використання LinkedList як черги:

import java.util.LinkedList;
import java.util.Queue;

public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();

// Додавання елементів до черги
queue.add(“Яблуко”);
queue.add(“Банан”);
queue.add(“Груша”);

// Отримання та видалення елементів з черги
System.out.println(queue.poll()); // Виведе “Яблуко” і видалить його
System.out.println(queue.peek()); // Виведе “Банан”, не видаляючи його

// Додавання і видалення як у двосторонній черзі
LinkedList<String> deque = new LinkedList<>();
deque.addFirst(“Львів”);
deque.addLast(“Одеса”);
System.out.println(deque.removeFirst()); // Виведе “Львів”
System.out.println(deque.removeLast()); // Виведе “Одеса”
}
}

Переваги LinkedList:

• Ефективні операції вставки/видалення: Операції додавання і видалення на початку або кінці списку є дуже швидкими (O(1)).
• Динамічність: Немає необхідності резервувати пам’ять заздалегідь, оскільки елементи додаються динамічно.
• Може бути використаний як стек, черга або список: Це робить `LinkedList` дуже гнучким інструментом для різних задач.

Недоліки:

• Повільний доступ за індексом: Операція доступу до елементів за індексом є повільною (O(n)), оскільки LinkedList не використовує масиви, а тому вимагає переходу по ланцюжку елементів.
• Більше використання пам’яті: Кожен елемент зберігає два посилання (на попередній і наступний елементи), що призводить до більшого використання пам’яті порівняно з масивами.

Висновок

• ArrayDeque — це ефективна структура даних для реалізації черг і стеків, яка забезпечує швидкий доступ і зміни на обох кінцях черги.
• LinkedList — універсальна структура, яка підходить для різних типів задач, включаючи реалізацію черг і списків, але може бути повільнішою при доступі до елементів за індексом.

Обидві структури мають свої переваги й недоліки залежно від задачі: для частих вставок і видалень на початку/кінці колекції варто використовувати LinkedList, тоді як для ефективного доступу до елементів підходить ArrayDeque.

Черги та клас ArrayDequeКлас LinkedList