Структура данных: Очередь

В понимании работы очереди нет ничего сложного. Мы практически каждый день сталкиваемся с очередями, например, в магазине у кассы. Как вы уже поняли, очередь отличается от стека порядком извлечения элементов. FIFO (First In First Out) – первый пришел, первый ушел. Все по честному. Ну, конечно если это не очередь в отечественных поликлиниках, где можно использовать волшебные слова “Я только спросить”. Ну да ладно, вернемся все таки к теме. Так же как и в повседневной жизни, очереди активно используются в работе самой операционной системы. Когда я набирал текст, который вы читаете, мне понадобилось воспользоваться текстовым редактором. Ровно в то время, когда я бил по клавиатуре, буквы, прежде чем попасть на экран, сохранялись в очереди и ждали освобождения процессора для выполнения операции по их записи в редакторе. И это лишь малая доля областей применения очередей. Так же можно вспомнить теорию массового обслуживания, различные паттерны.

Реализация очереди на языке Java.

Вывод

В очереди, как и в стеке мы написали те же методы insert(), remove(), peek(), isFull(), isEmpty(). Чуть более подробно разберем реализацию каждого метода. Тут есть тонкие моменты. Обратите внимания на цикличность очереди. Так как за основу мы используем для реализации массив, у которого, как нам известно, фиксированный размер, возможно настанет ситуация, когда мы достигнем конца массива, но при этом его начало будет пустым(мы уже извлекли несколько элементов из очереди). Этот случай мы учли в реализации методов insert() и remove(). 

insert(). При вставке элемента в очередь мы сначала проверяем, достиг ли указатель на хвост конца. Если да, то мы устанавливаем хвост в начальную позицию и вставляем элемент.

remove(). Когда же мы извлекаем элемент из очереди, мы кладем текущее значение во временную переменную и сдвигаем указатель головы выше. После проверяем, превышает ли указатель размер массива, и если так, то устанавливаем голову в начало, уменьшаем количество элементов в очереди и возвращаем сохраненное во временной переменной значение.

peek(). Тут все просто. Возвращаем значение, на которое указывает голова.

isEmpty(). Если элементов в очереди не осталось (их число равно 0), значит она пуста.

isFull(). Если количество элементов равно размеру массива, то очередь заполнена.

Обратим внимание на то, что в нашей реализации мы используем переменную для подсчета количества элементов в очереди. На самом деле можно реализовать очередь и без нее, однако тогда усложняться функции проверки пустоты и полноты очереди. У нас останется только указатели на хвост и голову, однако из-за цикличности возможны ситуации, такие что индекс хвоста будет меньше индекса головы. Необходимо брать это во внимание, если будете реализовывать свою очередь без счетчика элементов. Такая реализация будет уместной, если мы будет производить большое количество вставок и извлечений элементов на очереди больших размеров. В этой статье я не буду приводить ее реализацию, оставлю вам возможность самим написать очередь без счетчика элементов.

Еще одним интересным моментом в нашей очереди является то, что внутри методов insert() и remove() мы не делаем проверку на полноту/пустоту очереди. Оставляем все проверки на совесть пользователя. Хотя, конечно, пользователя лучше не грузить и предпочтительнее вставить проверки уже в функции, и в случае вставки в полную очередь и извлечения из пустой, выбрасывать сообщение с ошибкой. Так же предлагаю вам “поиграться” и добавить проверки внутрь функций.

Эффективность очереди такая же как и у стека O(1).

Оставить комментарий:

Ваш email не будет опубликован.