Блог для любопытных и не только
Структуры

Очереди

  • Название: Очередь (queue);
  • Применение: Способ хранения данных;
  • Время выполнения: Зависит от конкретной операции;
  • Сложность: Низкая;
  • Входные данные: Динамическая область памяти или массив;
  • Результат: Порядок данных по принципу FIFO ( First Input – First Output, «первым пришел – первым вышел»).

Пример из жизни:

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

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

Рассмотрим еще один пример, что происходит, когда человек нажимает клавишу на клавиатуре компьютера. Тем самым человек ожидает, что компьютер выполнить некоторое действие немедленно. И самый яркий пример — это банковская транзакция. Этот процесс очень сложный и приоритет операции задается последовательностью действий банковских операций. Следующее действие не будет выполнено, пока не выполнено предыдущее. Например, вы не можете оплатить покупку, если на вашем счету недостаточно средств.  Перейдем к формальному определению.

Определения:

Очередь (англ. queue)  — это абстрактная структура данных, в которой осуществляется следующий порядок добавления и извлечения элементов: первым из очереди извлекается элемент, который был помещен туда первым, то есть принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO).

То есть забирать элементы из очереди нужно в том же порядке, что и клали. Тут справедлива аналогия с реальной очередью или конвейером. Например, если записаны в очередь числа 1, 2, 3, то при последующем извлечении получим прямой порядок их поступления т.е. 1,2,3. Можно сказать, что порядок добавления не меняется на обратный, при извлечении. Можно сказать, что очередь противоположна стеку в этом плане.

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

Двусторонняя очередь (Double ended queue, deque) – очередь, у которой нет явно выраженного конца и начала. Она может расти и уменьшаться в обоих направлениях. В данном случае, будет рассмотрен классический случай т.е. односторонняя очередь (Queue).

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

Реализация:

Постановка задачи: Создать структуру данных, при которой добавление элемента осуществляет в его конец. Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, извлечение элемента  осуществляется только с головы  (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется. В простейшем случае, реализация данной структуры включает следующие опрерации: добавление нового элемента, извлечение элемента и чтение элемента.

Добавление элемента в очередь:

Шаг 1. Находится  последний элемент массива;

Шаг 2. Размер массива увеличивается на один элемент и добавляется элемент (если используется статический массив, размер, которого фиксирован и задается на этапе компиляции, находится последний занятый элемент массива и значение вставляется в следующую ячейку массива; при этом необходимо производить проверку на переполнение массива при каждой такой операции);

Извлечение из очереди:

Шаг 1. Находится первый элемент массива;

Шаг 2. Извлекается и сохраняется в промежуточную переменную;

Шаг 3. Данный элемент массива уничтожается;

Шаг 4. Массив пересчитывается, второй элемент становится первым, третий вторым и т.д.

Шаг 5. Возращается сохраненное значение.

Программная разработка:

В компилируемых языках программирования очереди можно представить, используя динамические области памяти или массивы. В большинстве языков программирования очередь реализован в виде готовых библиотек классов или функции. В php существуют различные функции и классы для реализации очереди:Классы PriorityQueue (очередь с приоритетом), Deque (двухстороняя очередь), Queue (одностророняя очередь). Так же функции для работы с массивом, как с очередью Извлекает первый элемент массива — array_shift — извлекает первый элемент массива и т.д.

Реализуем класс Queue, который обеспечивает функционал односторонней очереди. Задаются четыре свойства, которые позволяют обрабатывать данные в соотвествующем порядке. $head — голова или вершина очереди, $data — массив, который будет хранить элементы, $index_head — индекс первого элемента массива. Важный метод, который реализует функциональную возможность, в части извлечения головного элемента очереди — это dequeue(). В основе метода лежит поиск первого элемента массива. Ищется наименьший индекс массива, сохраняется (13 строка) в свойстве $head, затем уничтожается извлеченный элемент. getHead() — аналогичным способом ищется первый элемент массива, только без его удаления.

Время выполнения

  • Поиск — среднем O(1), худшем — O(n);
  • Вставка — среднем O(1), худшем — O(n);
  • Удаление — среднем O(1), худшем — O(n).
Список источников
Поделиться

Отправить ответ

avatar
wpDiscuz