Лекция
Привет, сегодня поговорим про очереди, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое очереди, очередь, циклическая очередь , настоятельно рекомендую прочитать все из категории Структуры данных.
очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO . Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.
Представление очереди FIFO (first in, first out)
Примеры:
Очередь писем для отправки пользователям.
Обработка загрузки файлов (ставится в очередь и поочередно загружается).
Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"— "сохранять", "retrieve" — "получать"). Функцияqstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В табл. 22.1 показано действие последовательности таких операций.
| Time complexity in big O notation | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|||||||||||||||||||||
Как известно, программы состоят из двух частей — алгоритмов и структур данных. В хорошей программе эти составляющие эффективно дополняют друг друга. Выбор и реализация структуры данных насколько же важны, как и процедуры для обработки данных. Способ организации и доступа к информации обычно определяется природой программируемой задачи. Таким образом, для программиста важно иметь в своем распоряжении приемы, подходящие для различных ситуаций.
На следующем уровне абстракции сугубо физические аспекты данных отходят на второй план вследствие введения механизма доступа(data engine) к данным, то есть механизма сохранения и получения информации. По существу, физические данные связываются с механизмом доступа, который управляет работой с данными из программы. Именно механизмам доступа к данным и посвящена эта глава.
Существует четыре механизма доступа:
Другие названия: магазин, стековая память, магазинная память, память магазинного типа, запоминающее устройство магазинного типа, стековое запоминающее устройство.
Другие названия: цепной список, список с использованием указателей, список со ссылками, список на указателях.
Другие названия: дерево двоичного поиска.
В этой статье вы познакомитесь с различными видами очередей. Всего существует 4 типа очередей. Коротко и с картинками о каждой.
<div style="box-sizing: inherit; color: rgb(74, 74, 74); font-family: BlinkMacSystemFont, -apple-system, " segoe="" ui",="" roboto,="" oxygen,="" ubuntu,="" cantarell,="" "fira="" sans",="" "droid="" "helvetica="" neue",="" helvetica,="" arial,="" sans-serif;="" font-size:="" 16px;"="">
Простая очередь подчиняется принципу FIFO: элемент вставляется в конец очереди, а удаляется из ее начала.
В круговой очереди последний элемент указывает на первый — это образует круг.
Главное преимущество кругового списка над обычным — более эффективное использование памяти. Если последняя позиция очереди занята, а первая пуста, элемент будет добавлен именно туда. В простых очередях сделать то же самое невозможно.
Очередь с приоритетом — тип очереди, в котором каждый элемент имеет свой приоритет. Порядок обслуживания элементов зависит от их приоритета. Если два элемента имеют одинаковый приоритет, то они обслуживаются в соответствии с их порядком в очереди.
Вставка зависит от переданного значения элемента. Удаление же происходит исходя из ее приоритета.
Двусторонняя очередь — тип очереди, в котором вставка и удаление элементов может происходить как с начала, так и с конца очереди. То есть, она не подчиняется принципу FIFO («первый пришел — первый вышел»)
| Действие | Содержимое очереди |
|---|---|
| qstore(A) | A |
| qstore(B) | А В |
| qstore(C) | A B C |
| qretrieve() возвращает А | В С |
| qstore(D) | B C D |
| qretrieve() возвращает В | C D |
| qretrieve() возвращает С | D |
Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Об этом говорит сайт https://intellect.icu . Поэтому после извлечения всех элементов очередь будет пуста.
В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.
Чтобы проиллюстрировать работу очереди, мы напишем простую программу планирования встреч. Эта программа позволяет сохранять информацию о некотором количестве встреч; потом по мере прохождения каждой встречи она удаляется из списка. Для упрощения описание встреч ограничено 255 символами, а количество встреч — произвольным числом 100.
При разработке этой простой программы планирования необходимо прежде всего реализовать описанные здесь функции qstore() иqretrieve(). Они будут хранить указатели на строки, содержащие описания встреч.
#define MAX 100
char *p[MAX];
int spos = 0;
int rpos = 0;
/* Сохранение встречи. */
void qstore(char *q)
{
if(spos==MAX) {
printf("Список переполнен\n");
return;
}
p[spos] = q;
spos++;
}
/* Получение встречи. */
char *qretrieve()
{
if(rpos==spos) {
printf("Встреч больше нет.\n");
return '\0';
}
rpos++;
return p[rpos-1];
}
Обратите внимание, что этим двум функциям требуются две глобальные переменные: spos, в которой хранится индекс следующего свободного места в списке, и rpos, в которой хранится индекс следующего элемента, подлежащего выборке. С помощью этих функций можно организовать очередь данных другого типа, просто поменяв базовый тип обрабатываемого ими массива.
Начальное сосотояние очереди
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('A')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('B')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A | B | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qretrive()
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | B | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qretrive()
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('A')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | C | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
|
Текст программы простого планировщика встреч целиком приведен ниже. Вы можете доработать эту программу по своему усмотрению.
/* Мини-планировщик событий */ #include #include #include #include #define MAX 100 char *p[MAX], *qretrieve(void); int spos = 0; int rpos = 0; void enter(void), qstore(char *q), review(void), delete_ap(void); int main(void) { char s[80]; register int t; for(t=0; t < MAX; ++t) p[t] = NULL; /* иницилизировать массив пустыми указателями */ for(;;) { printf("Ввести (E), Список (L), Удалить (R), Выход (Q): "); gets(s); *s = toupper(*s); switch(*s) { case 'E': enter(); break; case 'L': review(); break; case 'R': delete_ap(); break; case 'Q': exit(0); } } return 0; } /* Вставка в очередь новой встречи. */ void enter(void) { char s[256], *p; do { printf("Введите встречу %d: ", spos+1); gets(s); if(*s==0) break; /* запись не была произведена */ p = (char *) malloc(strlen(s)+1); if(!p) { printf("Не хватает памяти.\n"); return; } strcpy(p, s); if(*s) qstore(p); } while(*s); } /* Просмотр содержимого очереди. */ void review(void) { register int t; for(t=rpos; t < spos; ++t) printf("%d. %s\n", t+1, p[t]); } /* Удаление встречи из очереди. */ void delete_ap(void) { char *p; if((p=qretrieve())==NULL) return; printf("%s\n", p); } /* Вставка встречи. */ void qstore(char *q) { if(spos==MAX) { printf("List Full\n"); return; } p[spos] = q; spos++; } /* Извлечение встречи. */ char *qretrieve(void) { if(rpos==spos) { printf("Встречь больше нет.\n"); return NULL; } rpos++; return p[rpos-1]; }
Этот принцип имеет и другие названия: "первым пришел — первым обслужен", "в порядке поступления", "первым пришел — первым вышел", "обратного магазинного типа".
При изучении предыдущего примера программы планирования встреч, вероятно, вам в голову мог прийти следующий способ ее улучшения: при достижении конца массива, в котором хранится очередь, можно не останавливать программу, а устанавливать индексы вставки (spos) и извлечения (rpos) так, чтобы они указывали на начало массива. Это позволит помещать в очередь любое количество элементов при условии их своевременного извлечения. Такая реализация очереди называется циклической очередью, поскольку массив используется так, будто он представляет собой не линейный список, а кольцо.
Чтобы организовать в программе-планировщике циклическую очередь, функции qstore() и qretrieve() необходимо переписать следующим образом:
void qstore(char *q)
{
/* Очередь переполняется, когда spos на единицу
меньше rpos, либо когда spos указывает
на конец массива, а rpos - на начало.
*/
if(spos+1==rpos || (spos+1==MAX && !rpos)) {
printf("Список полон\n");
return;
}
p[spos] = q;
spos++;
if(spos==MAX) spos = 0; /* установить на начало */
}
char *qretrieve(void)
{
if(rpos==MAX) rpos = 0; /* установить на начало */
if(rpos==spos) {
printf("Встреч больше нет.\n");
return NULL;
}
rpos++;
return p[rpos-1];
}
В данной версии программы очередь переполняется, когда индекс записи находится непосредственно перед индексом извлечения; в противном случае еще есть место для вставки события. Очередь пуста, когда rpos равняется spos.
Вероятно, чаще всего циклические очереди применяются в операционных системах для хранения информации, учитываемой и записываемой в дисковые файлы или на консоль. Циклические очереди также используются в программах обработки реального времени, которые должны продолжать обрабатывать информацию, буферизируя при этом запросы на ввод/вывод. Многие текстовые процессоры используют этот прием во время переформатирования абзаца или выравнивания строки. Вводимый текст не отображается на экране до окончания процесса. Для этого прикладная программа должна проверять нажатие клавиш во время выполнения другой задачи. Если какая-либо клавиша была нажата, введенный символ быстро помещается в очередь, и процесс продолжается. После его завершения символы извлекаются из очереди.
Чтобы ощутить на практике данное применение циклических очередей, давайте рассмотрим простую программу, состоящую из двух процессов. Первый процесс в программе выводит на экран числа от 1 до 32 000. Второй процесс помещает символы в очередь по мере их ввода, не отображая их на экране, пока пользователь не нажмет . Вводимые символы не отображаются, поскольку первому процессу дан приоритет в отношении вывода на экран. После нажатия символы из очереди извлекаются и печатаются.
/* Пример циклической очереди в качестве буфера клавиатуры. */ #include #include #include #define MAX 80 char buf[MAX+1]; int spos = 0; int rpos = 0; void qstore(char q); char qretrieve(void); int main(void) { register char ch; int t; buf[80] = '\0'; /* Принимать вводимые символы до нажатия . */ for(ch=' ',t=0; t<32000 && ch!='\r'; ++t) { if(_kbhit()) { ch = _getch(); qstore(ch); } printf("%d ", t); if(ch == '\r') { /* Вывести на экран содержимое буфера клавиатуры и освободить буфер. */ printf("\n"); while((ch=qretrieve()) != '\0') printf("%c", ch); printf("\n"); } } return 0; } /* Занесение символа в очередь. */ void qstore(char q) { if(spos+1==rpos || (spos+1==MAX && !rpos)) { printf("Список полон\n"); return; } buf[spos] = q; spos++; if(spos==MAX) spos = 0; /* установить на начало */ } /* Получение символа из очереди. */ char qretrieve(void) { if(rpos==MAX) rpos = 0; /* установить на начало */ if(rpos==spos) return '\0'; rpos++; return buf[rpos-1]; }
Существует несколько способов реализации очереди в языках программирования.
Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.
Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдет новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив, и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.
Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.
Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.
Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.
Преимущества данного метода: размер очереди ограничен лишь объемом памяти.
Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.
Методы очереди могут быть реализованы на основе двух стеков S1 и S2, как показано ниже:
Процедура enqueue(x):
S1.push(x)
Функция dequeue():
если S2 пуст:
если S1 пуст:
сообщить об ошибке: очередь пуста
пока S1 не пуст:
S2.push(S1.pop())
вернуть S2.pop()
Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди
Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL также присутствует класс queue<>, определенный в заголовочном файле queue. В нем используется та же терминология (push и pop), что и в стеках.
| Характеристика | Очередь (Queue) | Стек (Stack) | Связанный список (Linked List) | Массив (Array) | Дек (Deque) | Куча (Heap) |
|---|---|---|---|---|---|---|
|
Принцип работы
|
FIFO (первый вошел — первый вышел) | LIFO (последний вошел — первый вышел) | Элементы связаны указателями | Индексы фиксированы | Доступ к обоим концам | Дерево, где родитель >= (max heap) или <= (min heap) дочерних элементов |
|
Добавление элементов
|
В конец (enqueue) | В конец (push) | В начало или конец | В любую позицию | В начало или конец | В корень (с балансировкой) |
|
Удаление элементов
|
Из начала (dequeue) | Из конца (pop) | В любой позиции (требует обхода) | В любой позиции (но требует сдвига) | В начало и конец | Из корня (с перестановкой) |
|
Доступ к элементам
|
Только к первому (head) | Только к последнему (top) | Последовательный (через ссылки) | Прямой доступ по индексу | В начало и конец | Только к корню (наибольший или наименьший элемент) |
|
Время работы (среднее)
|
O(1) (добавление/удаление) | O(1) (добавление/удаление) | O(1) (добавление в начало/конец) | O(1) (доступ), O(n) (вставка/удаление) | O(1) (операции с концами) | O(log n) (добавление, удаление, доступ к корню) |
| Где используется | Фоновые задачи, управление потоками, BFS-алгоритмы | Рекурсия, отмена действий (Ctrl+Z) | Динамические структуры, обход графов | Статические структуры, быстрый доступ | Буферы, парсеры, обработка данных | Очередь с приоритетами, алгоритмы Дейкстры и Хаффмана, хранение классов |
|
 |
 |
 |
 |
 |
Куча особенно полезна, когда нужно быстро находить наибольший или наименьший элемент
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нем и на первый незанятый элемент.
Очереди в веб-программировании используются для обработки задач асинхронно, распределения нагрузки и повышения производительности. Они помогают избежать долгих задержек в обработке запросов, позволяя выполнять сложные или ресурсоемкие операции в фоне.
Фоновая обработка задач
Отправка email-уведомлений
Генерация отчетов
Обработка изображений или видео
Балансировка нагрузки
Равномерное распределение нагрузки на сервер
Устранение пиковых нагрузок (например, при массовых запросах)
Повышение отказоустойчивости
Если сервер падает, задача не теряется, а обрабатывается позже
Возможность повторного выполнения задачи при сбоях
Обработка вебхуков и событий
Интеграция с внешними API (например, платежные системы)
Реализация event-driven архитектуры
Чат-боты и уведомления в реальном времени
Очередь сообщений для пользователей
Очередь событий для обработки данных в реальном времени
Redis (RQ, Celery, BullMQ) – быстрая и простая очередь на основе Redis
RabbitMQ – продвинутая система очередей на основе AMQP
Kafka – мощная распределенная очередь для обработки больших потоков данных
AWS SQS – облачное решение для очередей
На этом все! Теперь вы знаете все про очереди, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое очереди, очередь, циклическая очередь и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных