Очереди.

Очередь – это структура данных, во многом напоминающая стек. Но очередь, в отличие от стека реализуется по принципу FIFO (First In – First Out, т.е. первым пришел – первым вышел). По названию можно было догадаться, в чем состоит суть очереди. Здесь можно провести полную аналогию с нашей реальной жизнью. Все мы стоим в очередях – за хлебом, канцтоварами или авиабилетами. Люди, которые пришли и встали в очередь раньше остальных и обслуживаются первыми. Это справедливо, и по тому же принципу реализуется очередь, как структура данных, в информатике.

queue_art

 

Элементы очереди добавляются в ее конец. Также как и в случае со стеком, мы имеем доступ только к первому элементу, который должен быть обслужен. Вот как схематически можно изобразить принцип работы очереди:

queue

Что касается операций доступа к данным, то здесь все тоже самое: добавление элемента, чтение с вершины очереди и удаление из начала очереди.

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

Реализация во многом схожа со стеком. Мы также используем массив и храним ссылку на элемент, который находится в начале очереди. Также добавляется ссылка на элемент в конце очереди.

Теперь следует реализовать все три основные операции доступа к данным:

Добавление элемента в конец очереди.

Здесь мы выполняем предварительную проверку на предмет того, не достигло ли значение end конца массива. Если это так, то мы переносим маркер end в самое начало очереди, чтобы использовать пустые ячейки снова. На самом деле такая реализация очереди называется циклической очередью.

Извлечение элемента из вершины очереди.

Также реализуем два дополнительных метода, возвращающих размер очереди и результата проверки того, пуста ли очередь в данный момент.

Теперь протестируем все на примере. Вставим несколько элементов в нашу очередь, а потом последовательно выведем их на экран в порядке обслуживания:

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

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

Опишем структуру, представляющую очередь:

Теперь реализуем основные методы при работе с очередью:

А теперь пример с использованием очереди:

Двунаправленная очередь (дек).

Одна из разновидностей очередей разрешает удаление и вставку элементов с обеих сторон очереди, а не только с одной. В реализацию также следует добавить методы addFirst(), removeFirst(), addLast() и removeLast() для вставки и удаления первого и последнего элементов очереди. Вы можете попробовать реализовать эту задачу самостоятельно.

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

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