Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Вивчайте Структура Даних Черга в Java | Section
Фундаментальні структури даних у Java

Структура Даних Черга в Java

Свайпніть щоб показати меню

Почнемо з Queue. Уявіть собі чергу в магазині під час розпродажу. Є 10 людей; перша людина знаходиться ближче до дверей магазину, ніж інші, а десята людина — найдалі. Коли перша людина заходить у магазин, вона виходить із черги, тим самим зсуваючи всю чергу вперед на одну людину. Java Queue працює за дуже схожим принципом.

Таким чином можна реалізовувати різні програми, де логіка черги продумана. Наприклад, реалізація дошки з планами та завданнями.

Але спочатку розглянемо базові методи для роботи з Queue.

Queue — це інтерфейс, від якого наслідується клас LinkedList, з яким ви вже знайомі, тому ми будемо використовувати цю реалізацію.

Таким чином, ви використовуєте інтерфейс як тип об'єкта, але реалізацією об'єкта буде LinkedList, оскільки це конкретна реалізація цього об'єкта. (Пам'ятайте, що не можна створювати об'єкти на основі інтерфейсу).

Приклад:

Example.java

Example.java


              
1234

            
// `LinkedList` as implementation of the `List` interface:
List<T> list = new LinkedList<>(); 
// `LinkedList` as implementation of the `Queue` interface:
Queue<T> queue = new LinkedList<>();

Таким чином, можна зробити застосунок дуже гнучким, використовуючи різні реалізації одного й того ж інтерфейсу.

Але повернемося до методів роботи з Queue.

Методи

Деякі ключові методи інтерфейсу Queue:

  • add(element): додає елемент до черги, викидає виняток, якщо операція неможлива;
  • offer(element): додає елемент до черги, повертає true у разі успіху або false в іншому випадку.

Можна помітити, що ці методи по суті виконують одну й ту ж дію. Однак головна відмінність — це безпечність методу offer. У разі некоректного додавання елемента метод offer не викине виняток і не зупинить виконання програми.

Але наразі ця особливість не є для нас важливою, оскільки звичайна Queue не має обмежень. Проте існує структура BlockingQueue, яка має обмеження на кількість елементів; у такому випадку ці методи матимуть помітну різницю.

Розглянемо приклад:

Main.java

Main.java


              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.add("One");
        queue.add("Two");
        queue.add("Three");
        System.out.println("Queue: " + queue);
    }
}

Як видно, при використанні методу add() і спробі додати елемент, який не поміщається у чергу, програма викидає помилку та неочікувано завершує виконання.

Спробуємо виконати цю ж операцію, але з безпечнішим методом — offer():

Main.java

Main.java


              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
    }
}

Як бачите, тепер елемент не був доданий до черги, але також не було викинуто виняток. Тобто, можна вважати, що ми коректно обробили помилку.

Винятки можна обробляти по-іншому, використовуючи структуру на кшталт try-catch, але про це ми поговоримо пізніше.

Методи видалення

  • remove(): видаляє та повертає елемент з початку черги, викидаючи виняток, якщо черга порожня;
  • poll(): видаляє та повертає елемент з початку черги, повертаючи null, якщо черга порожня.

Ці методи виконують функцію так, ніби перша людина у черзі зайшла до магазину та покинула чергу. Саме тут діє принцип FIFO (First In, First Out — першим прийшов, першим пішов). Тобто, елемент, який був доданий першим до черги, буде першим видалений.

Тут також можна побачити різницю між цими двома методами. Метод poll() використовується частіше, ніж метод remove(), оскільки він є безпечнішим і не викидає винятків.

Розглянемо приклад:

Main.java

Main.java


              
123456789101112131415

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.remove();
        queue.remove();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Як бачите, програма викидає NoSuchElementException, оскільки ми намагаємося видалити елемент з порожньої черги.

Щоб уникнути такої виняткової ситуації, краще використовувати метод poll():

Main.java

Main.java


              
123456789101112131415

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.poll();
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Тепер ми безпечно видалили елемент з черги, і жодного винятку не було викинуто, коли ми спробували видалити елемент з порожнього списку.

Особливість повернення poll() методом null можна використати, наприклад, у циклі while().

Розглянемо приклад:

Main.java

Main.java


              
1234567891011121314151617181920

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.poll() != null) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Таким чином, можна видалити всі елементи з черги за допомогою циклу.

Зверніть увагу, що перший елемент, який потрапив у чергу, є тим, який видаляється! Наприклад, у наведеному вище прикладі першим було видалено елемент з даними "One".

Нижче продемонстровано принцип FIFO:

Main.java

Main.java


              
123456789101112131415161718

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);         
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Можемо перейти до методів, які повертають перший і останній елементи:

  • element(): повертає, але не видаляє елемент з початку черги, викидає виняток, якщо черга порожня;
  • peek(): повертає, але не видаляє елемент з початку черги, повертає null, якщо черга порожня.

Використання методу peek() є більш надійним і безпечним підходом, оскільки допомагає уникнути можливих винятків.

Розглянемо приклад використання:

Main.java

Main.java


              
12345678910111213141516

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
        System.out.println("The first element in the queue: " + queue.peek());
        System.out.println("Queue after the `peek()` method: " + queue);
    }
}

Можна поєднувати цей метод з іншими методами черги.

Якщо у вас є черга з п’яти елементів і потрібно видалити всі елементи до четвертого (включно), розглянемо реалізацію такої операції:

Main.java

Main.java


              
123456789101112131415161718192021

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (!queue.peek().equals("Four")) {
            queue.poll();
        }
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Було використано цикл з умовою на основі методу peek().

Цей цикл можна значно оптимізувати за допомогою методу contains(). Цей метод повертає true, якщо зазначений елемент присутній у черзі, і false, якщо його немає.

Покращимо наведений вище код:

Main.java

Main.java


              
1234567891011121314151617181920

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.contains("Four")) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Тут встановлено єдину умову для while циклу. Усі елементи, включно з елементом "Four", були успішно видалені.

1. Що таке Queue у Java?

2. Який інтерфейс представляє Queue у Java Collections Framework?

3. Яке призначення методу offer() в інтерфейсі Queue?

4. Що робить метод poll() в інтерфейсі Queue?

5. Який клас у пакеті Java java.util.concurrent представляє обмежену блокуючу чергу?

6. Що відбувається, якщо спробувати додати елемент до повної черги за допомогою методу add()?

question mark

Що таке Queue у Java?

Виберіть правильну відповідь

question mark

Який інтерфейс представляє Queue у Java Collections Framework?

Виберіть правильну відповідь

question mark

Яке призначення методу offer() в інтерфейсі Queue?

Виберіть правильну відповідь

question mark

Що робить метод poll() в інтерфейсі Queue?

Виберіть правильну відповідь

question mark

Який клас у пакеті Java java.util.concurrent представляє обмежену блокуючу чергу?

Виберіть правильну відповідь

question mark

Що відбувається, якщо спробувати додати елемент до повної черги за допомогою методу add()?

Виберіть правильну відповідь

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 1. Розділ 9

Запитати АІ

expand

Запитати АІ

ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 1. Розділ 9
some-alt