Пишем очередь на Java

Очередь на Java. Теория

Структура данных, которая называется в информатике очередь, несколько напоминает стек, но в очереди первым изымается элемент, вставленный первым. (Способ организации данных FIFO, First-In-First-Out), в то время как в стеке мы видели, что первым изымался тот элемент, который вставлялся последним (способ организации данных LIFO, Last-In-First-Out).

Очередь работает по тому же принципу как и любая очередь в кино (человек, который первым встал в очередь, первым дойдет до кассы и купит билет). Соответственно тот кто станет в очередь последним, купит билет последним (или не купит его вообще, если все билеты будут распроданы).

Очередь — такой же вспомогательный инструмент программиста, как и стек. Они используются для моделирования реальных ситуаций ожидания клиентов в банке, вылета самолетов или передачи данных по Интернету.

Где используется очередь?

В операционной системе Вашего компьютера (и в сети интернет) постоянно работают различные очереди, незаметно исполняющие свои обязанности.

Например, в очереди печати — документы ждут освобождения принтера. Данные вводимые с клавиатуры, также хранятся в очереди.

Если вы работаете в текстовом редакторе, а компьютер отвлекается на выполнение другой операции, то нажатые будут ждать в очереди, пока у редактора не явится свободное время для их получения.

Реализация очереди

Проиллюстрируем нашу очередь. Первый элемент в очереди назовем Front, элемент который находит в очереди последним — Rear. Основой нашей очереди будет классический массив.

1

Две основные операции с очередью, это: вставка элемента в конец очереди и удаления элемента из начала очереди.

Графическая иллюстрация вставки элемента (вставляем число 7):

2

Удалим элемент из начала очереди (321):

3

Стоит рассмотреть такое явление, как циклический перенос. При вставки нового элемента, маркер Front смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Rear также смещается вверх. Проблема в том, что даже если в начале массива будут пустые ячейки, из которых были удалены элементы, вставить новый элемент не получится, потому что маркера Rear некуда двигаться дальше. Проиллюстрируем эту ситуацию:

4

Для решения этой проблемы со вставкой в ​​очередь в которой имеются свободные ячейки, маркеры Front и Rear при достижении границы массива перемещаются до его начала. Такая структура данных называется циклической очередь (или кольцевым буфером).

5

Пример очереди (Queue) на Java

Реализуем очередь на базе массива. Объявим и инициализирует переменные:

Реализуем метод вставки элемента в очередь (с использованием циклического переноса):

Реализуем метод удаления элемента из начала очереди (с использованием циклического переноса):

На всякий случай вот вам список нужных гетер и методов проверки очереди на переполнение или пустоту:

Реализуем метод main и применим вышеуказанные методы:

Итак мы видим, что все работает правильно. Сначала вставляем элементы 10, 20, 30, 40, 50. Следующие 3 выполнения метода remove() оставят в нашей очереди 40, 50. И наконец добавляем в очередь 60 и получаем 40, 50, 60.

Следите за обновлениями.

One thought to “Пишем очередь на Java”

  1. У Вас написано
    «При вставки нового элемента, маркер Front смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Rear также смещается вверх.»

    Правильней будет так
    «При вставки нового элемента, маркер Rear смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Front также смещается вверх.»

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *