Очередь
Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций [math] \mathtt [/math] и [math] \mathtt [/math] соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
- [math] \mathtt [/math] — проверка очереди на наличие в ней элементов,
- [math] \mathtt [/math] (запись в очередь) — операция вставки нового элемента,
- [math] \mathtt [/math] (снятие с очереди) — операция удаления нового элемента,
- [math] \mathtt [/math] — операция получения количества элементов в очереди.
Реализация циклической очереди на массиве
Очередь, способную вместить не более [math]\mathtt[/math] элементов, можно реализовать с помощью массива [math]\mathtt
- [math]\mathtt[/math] — голова очереди,
- [math]\mathtt[/math] — хвост очереди.
empty
boolean empty(): return head == tail
push
function push(x : T): if (size() != n) elements[tail] = x tail = (tail + 1) % n
pop
T pop(): if (empty()) return null x = elements[head] head = (head + 1) % n return x
size
int size() if head > tail return n - head + tail else return tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за [math]O(1)[/math] времени.
- проста в разработке,
- по сравнению с реализацией на списке есть незначительная экономия памяти.
- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
Реализация на списке
Для данной реализации очереди необходимо создать список [math]list[/math] и операции работы на созданном списке.
Реализация очереди на односвязном списке:
List
- ListItem(data : T, next : ListItem) — конструктор,
- [math]\mathtt[/math] — поле, в котором хранится значение элемента,
- [math]\mathtt[/math] — указатель на следующий элемент очереди.
push
function push(x : T): element = tail tail = ListItem(x, NULL) if size == 0 head = tail else element.next = tail size++
pop
T pop(): size-- element = head head = head.next return element
empty
boolean empty(): return head == tail
- каждая операция выполняется за время [math]O(1)[/math] .
- память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
Реализация на двух стеках
Очередь можно реализовать на двух стеках [math]\mathtt[/math] и [math]\mathtt[/math] . Поступим следующим образом: [math]\mathtt[/math] будем использовать для операции [math] \mathtt [/math] , [math]\mathtt[/math] для операции [math] \mathtt [/math] . При этом, если при попытке извлечения элемента из [math]\mathtt[/math] он оказался пустым, просто перенесем все элементы из [math]\mathtt[/math] в него (при этом элементы в [math]\mathtt[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]\mathtt[/math] станет пустым).
- [math] \mathtt [/math] и [math] \mathtt [/math] — функции, реализующие операцию [math] \mathtt [/math] для соответствующего стека,
- [math] \mathtt [/math] и [math] \mathtt [/math] — аналогично операции [math] \mathtt [/math] .
push
function push(x : T): pushLeft(x)
pop
T pop(): if not rightStack.empty() return popRight() else while not leftStack.empty() pushRight(popLeft()) return popRight()
При выполнении операции [math] \mathtt [/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math] \mathtt [/math] из первого стека, третью во второй стек на финальный [math] \mathtt [/math] . Тогда для операций [math] \mathtt [/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math] \mathtt [/math] .
Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math] .
- эту реализацию несложно модифицировать для получения минимума в текущей очереди за [math]O(1)[/math] .
- если [math]\mathtt[/math] не пуст, то операция [math] \mathtt [/math] может выполняться [math]O(n)[/math] времени, в отличие от других реализаций, где [math] \mathtt [/math] всегда выполняется за [math]O(1)[/math] .
Реализация на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.
Подробное описание в статье Персистентная очередь.
Отличия от других реализаций
- [math]O(1)[/math] реального времени на операцию,
- возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
- дольше в среднем выполняются операции,
- больше расход памяти,
- большая сложность реализации.
См. также
Источники информации
- Википедия — Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
- Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980
Очереди в программировании. Просто о сложном
Распространенная ошибка начинающих разработчиков — это избыточная функциональность, выполняющаяся за один запрос. Бывает, что за единичный запрос разработчик пытается выполнить: создание записи в бд, загрузку видео, создание превью, и отправку уведомления по почте. Звучит страшно, но на практике бывает часто. Потому, сегодня, моей целью будет открыть для вас ещё одну продвинутую технологии, именуемой «очередью».
Представьте, что вы владелец сайта фотогалереи. И каждый пользователь может загрузить несколько картинок за один раз. Задача скрипта состоит в том, чтобы обработать все картинки, загруженные пользователем, и создать превью маленького размера для каждой из них.
Если, при загрузке, пользователь выберет одно, или два изображения, то он не будет ждать слишком долгого окончания загрузки и ответ сервера будет достаточно комфортным. Но, представьте, что случится, если пользователь попытается загрузить целую папку из 10, а то и 30 картинок. То мало того, что он будет ждать, пока все превьюхи сгенерируются, так ещё, и при единственной ошибке, загружать всё придётся по-новому.
Браузер безпроблемно поддерживает многофайловую загрузку. Это удобно, и существенно повышает юзабилити на сайте. Так, вместо многоразового скроллинга, и выбора файла, можно указать за один раз все необходимые. Это отличная функция на клиенте, однако, стоит научиться работать с многофайловой загрузкой на самом сервере.
Синхронная загрузка в этом случае — это не лучшее решение. Потому как, из него вытекают последствия в виде долгой загрузки страницы, и прерывание обработки при закрытии страницы. Вместо этого, пользователю можно позволить загрузить множество картинок, а создание их превьюшек делать уже отдельно, в фоне. Пример повседневного применения очереди:
youtube — при загрузке личного видео, оно становится доступным только через какое-то время, т.е. когда обработается в фоне;
vk — при загрузке песни, или видео, аналогично, становится доступным не сразу после загрузки, а только после обработки.
Жизненный цикл загрузки файлов без очереди
Обычный процесс загрузки выглядит так:
Исходя из этой картинки, можно понять, что при таком подходе, может возникнуть множество ситуаций, при которых скрипт отработает неправильно.
Основные проблемы, которые могут возникнуть, когда:
- Пользователь отменит загрузку, закрыв вкладку
- Пользователю надоест ожидать долгую работу скрипта, и он отменит загрузку
- Соединение будет разорвано браузером по таймауту
И при любой из этих ошибок, пользователь будет необходимо повторить загрузку заново. А, поверьте мне, не каждый пользователь вытерпит загрузку изображений в виде лотереи, и уйдёт с вашего сайта после первой-второй такой ошибки.
Не исключая и благоприятный исход, пользователь будет продолжать пользоваться вашим сервисом, так что это тоже имеет право на жизнь.
PHP + очередь
Что же, а как тогда будет выглядеть схема работы PHP с очередью? Просто:
Из картинки можно увидеть, что там изображено 3 очереди, каждая из которых работает отдельно над своей задачей: обработка изображений , видео , и отправка email писем .
Как только пользователь завершает загрузку изображений, в очередь добавляется новая задача, и выполняется. Воркер очереди картинок видит новую задачу, и начинает генерировать их превью.
Вы же, на стороне клиента можете показать сообщение «мы обрабатываем ваши изображения, ожидайте«, а в то время, пока они будут обрабатываться пользователь безпрепяственно может просматривать любые страницы вашего приложения. Теперь вы даете возможность пользователю провести больше времени с пользой на вашем сайте, пока процессы работают в фоне. Пользователь может делать что угодно, даже добавлять новые изображения :).
Воркер обрабатывает задачи настолько быстро, насколько это возможно. Если будет загружено 5 картинок, то задача будет выполнена быстро, если 1000, то это займёт какое-то время. Но, зато, теперь пользователь это время обработки может потратить более полезно, чем при стандартном решении.
В результате, по завершению работы, воркер может сразу же оповестить пользователей. Каким способом отправлять уведомления — это всё на ваш выбор. Можете оповещать по вебсокетам, по email, или обычные оповещения после перезагрузки страницы.
После выполнения всех заданий из очереди, воркер опять начинает ожидать новые задачи.
Остальные 2 воркера, которые были показаны выше, в это время, не делают никакой работы, пока в их очереди нет задач. Но, как только они получают в пул новые, то сразу же обрабатывают их, в зависимости от вашей программной реализации.
Больше очередей
Более того, вы можете создавать целую цепочку очередей. К примеру, изнутри самой очереди обработки картинок, вы можете добавить новую задачу в очередь на отправку email письма.
Это вы можете увидеть на примере предыдущей картинки, немного видоизменённой:
Здесь показано, что, как только воркер завершит свою работу, будет создана новая задача по отправке письма, в другой очереди. В свою очередь, email-воркер уже отрабатывает, и оповещает пользователя о завершении работы над изображениями.
До сих пор непонятно?
Если вы всё ещё до конца не понимаете, что такое очередь, и как они работают, то, этот раздел для вас. Уйдём от примеров из программирования, и рассмотрим бытовой пример. Представьте, что вы позвонили в кафе, чтобы заказать пиццу. От готовой пиццы и у вас на столе, вас отделяет несколько шагов:
- Кто-то принимает ваш заказ, и начинает готовить пиццу (добавляя нужные ингредиенты, соусы, и т.д.)
- Запаковывает в коробку, и едет по адресной доставке.
- На месте, вы уже расплачиваетесь с курьером, и получаете свою пиццу.
Представьте, насколько долгим будет этот процесс, если только один работник будет выполнять все задачи. Конечно, если у него только один заказ в день, то звучит не так плохо. Но что случится, если он получит 5 заказов течении одной минуты? Очевидно, что сил одного тут будет слишком мало, и этот работник будет перегружен.
В результате, некоторые из заказов могут потеряться, в некоторых могут несоответствовать ингредиенты тем, что заказывали. Или, когда доставка производится в 5 разных мест, они могут находиться слишком далеко друг от друга, что повлечёт за собой опоздание курьера, и еда клиентов станет холодной.
Но, с точки зрения очереди, эту ситуацию можно пересмотреть. Давайте представим, что теперь работник не один, а несколько, и у каждого есть своя задача.
- Один человек ждёт входящие звонки, и принимает заказы
- Второй готовит пиццу
- И третий осуществляет доставку пиццы по адресу
И в итоге, когда каждый имеет чёткие обязанности, и занят только одним делом, то меньше вероятность ошибки, и процесс создания продукта является более оптимизированным.
На этом простом примере, можно вывести понятие очереди.
Очередь — это последовательное выполнение списка задач в фоне. При том, что воркеров (выполняющих задачи из очереди) может быть много, каждый отвечающий за свою типовую задачу. На примере пиццерии — каждый работник имеет свои обязанности, которые и выполняет (это и есть воркеры).
Резюме
В этой статье я описал принцип работы очереди, что такое php очередь, и что из себя представляет php сервер очередей. Здесь была разобрана только теория, без привязки к конкретному языку программирования. Для полного понимания, подготовлена практическая статья с реализацией php скрипта работы с очередью.
В серці. Назавжди.
Вчора у мене помер однокласник. А сьогодні бабуся. І хто б міг уявити, що цей рік принесе війну, смерть товариша, та смерть члена сім’ї? Це боляче. Проте це добре нагадування про те, як швидко тече час. І як його ціна збільшується кожної марно витраченої секунди. І я не скажу щось
20 мая 2022 г. 1 min read
Ось такий він, руський мир
«Руський мир» — звучить дуже сильно та виправдовуюче. Гарна обгортка виправдання слабкості, аморальності та нікчемності своїх дійсних намірів. Руський мир, який дуже солодко звучить для всіх, хто хоче закрити очі на факт повномасштабної війни. Дуже добре виправдання вбивства для купки звірів. Втім, це ж росія, в якій все виглядає логічно
16 апр. 2022 г. 3 min read
Перехват запросов и ответов JavaScript Fetch API
Перехватчики — это блоки кода, которые вы можете использовать для предварительной или последующей обработки HTTP-вызовов, помогая в обработке глобальных ошибок, аутентификации, логирования, изменения тела запроса и многом другом. В этой статье вы узнаете, как перехватывать вызовы JavaScript Fetch API. Есть два типа событий, для которых вы можете захотеть перехватить HTTP-вызовы:
Информатика. 10 класс (Повышенный уровень)
В информатике структура данных — программная единица, позволяющая хранить и обрабатывать данные, а также обеспечивающая их эффективное использование. Данные при этом должны быть однотипными или логически связанными.
Различные виды структур данных подходят для различных задач; некоторые из них имеют узкую специализацию, другие являются универсальными (пример 21.1).
При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят не только от выбора алгоритма, но и от правильного выбора структур данных. Одни и те же данные можно сохранить в структурах, требующих различного объема памяти, а алгоритмы работы с разными структурами данных могут иметь различную эффективность. Структура данных, наиболее подходящая для решения конкретной задачи, позволяет выполнять большое количество различных операций, используя как можно меньший объем ресурсов.
Ни одна профессиональная программа сегодня не пишется без использования структур данных, поэтому многие из них содержатся в стандартных библиотеках современных языков программирования (например, STL для С++).
Структура данных представляет собой набор значений данных, отношения между ними, а также функции и (или) операции, которые могут быть применены к данным.
Структуры данных классифицируют по разным признакам. В примере 21.2 приведена классификация структур данных по организации взаимосвязей между элементами.
Пример 21.1. Примеры некоторых структур данных:
1. Массив (вектор в C++) — самая простая и широко используемая структура данных.
2. Запись (структура в С++) — совокупность элементов данных разного типа. Содержит постоянное количество элементов, которые называют полями.
3. Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном.
4. Граф — совокупность вершин (узлов) и связей между ними (ребер). В реальной жизни по такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения.
5. Множество — совокупность данных, значения которых не повторяются, реализация математического объекта множество, за исключением того, что множество в программировании конечно.
Пример 21.2. Классификация структур данных.
-
- массив;
- список;
- связанный список;
- стек;
- очередь;
- хэш-таблица.
Иерархические:
-
- двоичные деревья;
- n-арные деревья;
- иерархический список.
-
- неориентированный граф;
- ориентированный граф.
-
- таблица реляционной базы данных;
- двумерный массив.
Очередь
Представьте себе очередь в кассу кинотеатра. Кто раньше пришел, тот раньше получит билет. Так и в программировании.
Очередь подчиняется принципу FIFO — Firts In First Out («первый пришел — первый вышел»). Первый элемент в очереди выходит первым.
Как видите, элемент 1 поступил в очередь до 2 и удалился первым — это и есть принцип FIFO.
Enqueue — метод, который добавляет элемент в очередь. Dequeue , наоборот, удаляет его.
Реализовать очередь можно в любом языке — С, С++, Java, Python или C#. Во всех языках очереди очень похожи.
Как работает очередь
Очередь работает следующим образом:
- Реализуется два указателя — FRONT и REAR .
- FRONT — указатель на первый элемент очереди.
- REAR — указатель на последний элемент очереди.
- Значения FRONT и REAR изначально должны быть равны -1.
Базовые операции с очередями
Очередь — объект (абстрактный тип данных. Он поддерживает такие операции:
- Enqueue — позволяет добавить элемент в конец очереди.
- Pop — позволяет удалить элемент из начала очереди.
- IsEmpty — проверяет, пуста ли очередь.
- IsFull — проверяет, заполнена ли очередь.
- Peek — позволяет получить элемент в начале очереди без его удаления.
Операция enqueue
- Проверьте, не полна ли очередь.
- При добавлении первого элемента присвойте значение 0 указателю FRONT
- Увеличьте значение REAR на 1.
- Добавьте новый элемент на позицию, куда указывает REAR .
Операция dequeue
- Проверьте, не пуста ли очередь.
- Получите значение, на которое указывает FRONT .
- Увеличьте значение FRONT на 1.
- При удалении последнего элемента присвойте значение -1 указателям FRONT и REAR .
Реализация очередей
В Java и С++ очереди реализуются с помощью массивов. В Python — с помощью списков.
Python
# Реализация очередей в Python class Queue: def __init__(self): self.queue = [] # Добавляем элемент def enqueue(self, item): self.queue.append(item) # Удаляем элемент def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Выводим очередь в консоль def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("После удаления элемента") q.display()Java
// Реализация очередей в Java public class Queue < int SIZE = 5; int items[] = new int[SIZE]; int front, rear; Queue() < front = -1; rear = -1; >boolean isFull() < if (front == 0 && rear == SIZE - 1) < return true; >return false; > boolean isEmpty() < if (front == -1) return true; else return false; >void enQueue(int element) < if (isFull()) < System.out.println("Очередь заполнена"); >else < if (front == -1) front = 0; rear++; items[rear] = element; System.out.println("Добавлен элемент " + element); >> int deQueue() < int element; if (isEmpty()) < System.out.println("Очередь пуста"); return (-1); >else < element = items[front]; if (front >= rear) < front = -1; rear = -1; >/* Внутри Q только один элемент, поэтому очередь сбрасывается в начальное состояние после удаления последнего элемента */ else < front++; >System.out.println("Удален элемент -> " + element); return (element); > > void display() < /* Функция выводит элементы очереди в консоль */ int i; if (isEmpty()) < System.out.println("Пустая очередь"); >else < System.out.println("\nИндекс FRONT->" + front); System.out.println("Элементы -> "); for (i = front; i " + rear); > > public static void main(String[] args) < Queue q = new Queue(); // функцию deQueue нельзя применять к пустой очереди q.deQueue(); // Добавляем в очередь 5 элементов q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Шестой элемент добавить нельзя — очередь заполнена q.enQueue(6); q.display(); // Функция deQueue удаляет первый элемент — 1 q.deQueue(); // Теперь внутри очереди 4 элемента q.display(); >>C
// Реализация очередей в C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items[SIZE], front = -1, rear = -1; int main() < //функцию deQueue нельзя применять к пустой очереди deQueue(); // Добавляем в очередь 5 элементов enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // Шестой элемент добавить нельзя — очередь заполнена enQueue(6); display(); // Функция deQueue удаляет первый элемент — 1 deQueue(); // Теперь внутри очереди 4 элемента display(); return 0; >void enQueue(int value) < if (rear == SIZE - 1) printf("\nОчередь заполнена"); else < if (front == -1) front = 0; rear++; items[rear] = value; printf("\nДобавлено значение ->%d", value); > > void deQueue() < if (front == -1) printf("\nОчередь пуста"); else < printf("\nУдален элемент: %d", items[front]); front++; if (front >rear) front = rear = -1; > > // Функция выводит очередь в консоль void display() < if (rear == -1) printf("\nОчередь пуста"); else < int i; printf("\nЭлементы очереди:\n"); for (i = front; i printf("\n"); >C++
// Реализация очередей в C++ #include #define SIZE 5 using namespace std; class Queue < private: int items[SIZE], front, rear; public: Queue() < front = -1; rear = -1; >bool isFull() < if (front == 0 && rear == SIZE - 1) < return true; >return false; > bool isEmpty() < if (front == -1) return true; else return false; >void enQueue(int element) < if (isFull()) < cout else < if (front == -1) front = 0; rear++; items[rear] = element; cout > int deQueue() < int element; if (isEmpty()) < cout else < element = items[front]; if (front >= rear) < front = -1; rear = -1; >/* Внутри Q только один элемент, поэтому очередь сбрасывается в начальное состояние после удаления последнего элемента */ else < front++; >cout " > void display() < /* Функция выводит в консоль элементы очереди */ int i; if (isEmpty()) < cout else < cout " "; for (i = front; i " > >; int main() < Queue q; // функцию deQueue нельзя применять к пустой очереди q.deQueue(); // Добавляем 5 элементов q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Шестой элемент добавить нельзя — очередь заполнена q.enQueue(6); q.display(); // Функция deQueue удаляет первый элемент — 1 q.deQueue(); // Теперь внутри очереди 4 элемента q.display(); return 0; >Недостатки очереди
Рассмотрите картинку ниже. Вы можете заметить, что после нескольких операция удаления и добавления элементов размер очереди увеличивается.
Теперь использовать индексы 0 и 1 мы не можем — очередь нужно сбросить в изначальное состояние, т. е. удалить все элементы из очереди.
Существует модификация очереди, исправляющая этот недостаток — круговая очередь. Она позволяет сместить указатель REAR , когда он достигает конца очереди. Благодаря этому мы можем вновь использовать освободившееся пространство.
Временная сложность очередей
Сложность операций enqueue и dequeue очереди, реализованной с помощью массивов, — O(1) .
Где применяются очереди
- Планирование процессов и работы жесткого диска.
- Для синхронизации данных, перемещаемых между двумя процессами. Например: буферы ввода-вывода, конвейеры, файловые буферы ввода-вывода и т. д.
- Обработка прерываний в системах реального времени .
- Телефоны в колл-центрах используют очереди, чтобы обслуживать клиентов по порядку.
СodeСhick.io - простой и эффективный способ изучения программирования.
2024 © ООО "Алгоритмы и практика"