Продолжаем изучать алгоритмы.
Очередь — это почти то же самое, что и стек, но тут первым извлекается тот элемент, который был вставлен первым. Всё работает по принципу FIFO (First-In-First-Out). Напомню, что в стеке берется элемент, который был последним (LIFO — Last-In-Last-Out).
Если стек — это пачка писем, то очередь — это самая обычная очередь (например, за билетами в кино). Тот, кто первым встал в очередь, тот первым и получит услугу. Кто последним встал — последним получит.
Сложность очереди: вставка и получение выполняется за О(1). Всё как в стеке.
Пример очереди на котлине:
Очередь реализована на базе массива, поэтому внутрь передаем размер массива.
Пройдемся по методам и переменным:
front — первый элемент в очереди. Если первый человек в очереди получает билет и уходит, то теперь второй человек считается первым. Если второй человек тоже получает билет, то он уходит и теперь третий человек считается первым. Поэтому будем увеличивать front при удалении из очереди.
items — количество элементов, которые есть в массиве. Это именно количество вставленных элементов, а не размер массива. Если очередь рассчитана на 5 человек, но пока что там стоит только 1 человек, то items = 1.
rear — место, куда будем вставлять элемент. Если rear = items, т.е. массив заполнен, то обнуляем rear, чтобы в следующий раз вставить на нулевое место. В самом начале rear = -1. Когда подходит первый человек, то увеличиваем rear и человек встает на нулевое место (в массивах нумерация с нуля). Когда подходит второй человек, то увеличиваем rear и человек встает на первое место. Если заполнены все пять мест и подходит еще один человек, то мы ставим его нулевое место и так по кругу — случай, когда все люди в очереди получили свои билеты и все начинается сначала.
insert() — предполагаем, что очередь не заполнена. По-хорошему, тут надо бы предварительно вызвать isFull(). Можно обрабатывать внутри очереди (например, бросать исключение) или проверять в main. При вставке нового элемента увеличиваем rear и новый элемент вставляем для нового значения rear. В конце увеличиваем количество элементов.
remove() — аналогично считаем, что очередь не пустая. Сначала увеличиваем переменную front (выше объясняла зачем) и потом во временную переменную сохраняем значения для нового front. Если front уходит за пределы массива, то обнуляем. Уменьшаем количество элементов items и возвращаем временную переменную (как раз она и удалена).
peek() — просто возвращаем значение из ячейки front.
isEmpty() — возвращает true, если очередь пустая.
isFull() — возвращает true, если очередь полная.
size() — количество элементов в очереди.
P.S. По мотивам Роберта Лафоре "Структуры данных и алгоритмы в Java"
