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

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

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

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

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

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

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

Приклад:

Example.java

Example.java

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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?

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

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

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

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

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

Запитати АІ

expand

Запитати АІ

ChatGPT

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

Suggested prompts:

Can you explain more about the difference between add() and offer() methods?

How does the FIFO principle work in a real-world queue?

What are some practical uses of the Queue interface in Java?

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

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

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

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

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

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

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

Приклад:

Example.java

Example.java

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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

copy

              
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?

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

question mark

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

Select the correct answer

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

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

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

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