Лекция
Привет, сегодня поговорим про очереди, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое очереди, очередь, циклическая очередь , настоятельно рекомендую прочитать все из категории Структуры данных.
очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO . Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.
Представление очереди FIFO (first in, first out)
Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"— "сохранять", "retrieve" — "получать"). Функцияqstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В табл. 22.1 показано действие последовательности таких операций.
| Time complexity in big O notation | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|||||||||||||||||||||
Как известно, программы состоят из двух частей — алгоритмов и структур данных. В хорошей программе эти составляющие эффективно дополняют друг друга. Выбор и реализация структуры данных насколько же важны, как и процедуры для обработки данных. Способ организации и доступа к информации обычно определяется природой программируемой задачи. Таким образом, для программиста важно иметь в своем распоряжении приемы, подходящие для различных ситуаций.
Степень привязки типа данных к своему машинному представлению находится в обратной зависимости от его абстракции. Другими словами, чем более абстрактными становятся типы данных, тем больше концептуальное представление о способе хранения этих данных отличается от реального, фактического способа их хранения в памяти компьютера Простые типы, например, char или int, тесно связаны со своим машинным представлением. Например, машинное представление целочисленного значения хорошо аппроксимирует соответствующую концепцию программирования. По мере своего усложнения типы данных становятся концептуально менее похожими на свои машинные эквиваленты. Так, действительные числа с плавающей точкой более абстрактны, чем целые числа. Фактическое представление типа float в машине весьма приблизительно соответствует представлению среднего программиста о действительном числе. Еще более абстрактной является структура, принадлежащая к составным типам данных.
На следующем уровне абстракции сугубо физические аспекты данных отходят на второй план вследствие введения механизма доступа(data engine) к данным, то есть механизма сохранения и получения информации. По существу, физические данные связываются с механизмом доступа, который управляет работой с данными из программы. Именно механизмам доступа к данным и посвящена эта глава.
Существует четыре механизма доступа:
Каждый из этих методов дает возможность решать задачи определенного класса. Эти методы по существу являются механизмами, выполняющими определенные операции сохранения и получения передаваемой им информации на основе получаемых ими запросов. Они все сохраняют и получают элемент, здесь под элементом подразумевается информационная единица. В этой главе показано, как создавать такие механизмы доступа на языке С. При этом проиллюстрированы некоторые распространенные приемы программирования в С, включая динамическое выделение памяти и использование указателей.
Другие названия: магазин, стековая память, магазинная память, память магазинного типа, запоминающее устройство магазинного типа, стековое запоминающее устройство.
Другие названия: цепной список, список с использованием указателей, список со ссылками, список на указателях.
Другие названия: дерево двоичного поиска.
<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 |
Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста.
В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.
Чтобы проиллюстрировать работу очереди, мы напишем простую программу планирования встреч. Эта программа позволяет сохранять информацию о некотором количестве встреч; потом по мере прохождения каждой встречи она удаляется из списка. Для упрощения описание встреч ограничено 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, в которой хранится индекс следующего элемента, подлежащего выборке. С помощью этих функций можно организовать очередь данных другого типа, просто поменяв базовый тип обрабатываемого ими массива.
Функция qstore() помещает описания новых встреч в конец списка и проверяет, не переполнен ли список. Функция qretrieve()извлекает встречи из очереди, если таковые имеются. При назначении встреч увеличивается значение переменной spos, а по мере их прохождения увеличивается значение переменной rpos. По существу, rpos "догоняет" spos в очереди. На рис 22.1 показано, что может происходить в памяти при выполнении программы. Если rpos и spos равны, назначенные события отсутствуют. Даже несмотря на то, что функция qretrieve() не уничтожает хранящуюся в очереди информацию физически, эту информацию можно считать уничтоженной, так как повторно получить доступ к ней невозможно.
Рис. 22.1. Индекс выборки "догоняет" индекс вставки
Начальное сосотояние очереди
↓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. Второй процесс помещает символы в очередь по мере их ввода, не отображая их на экране, пока пользователь не нажмет . Вводимые символы не отображаются, поскольку первому процессу дан приоритет в отношении вывода на экран. После нажатия символы из очереди извлекаются и печатаются.
Чтобы программа работала, как описано выше, в ней необходимо использовать две функции, не определенные в стандартном языке С:_kbhit() и _getch(). Функция _kbhit() возвращает значение ИСТИНА, если на клавиатуре была нажата клавиша; в противном случае она возвращает ЛОЖЬ. Функция _getch() считывает введенный символ, но не дублирует его на экране. В стандарте языка С не предусмотрены функции для проверки состояния клавиатуры или считывания символов без отображения на экране, поскольку эти функции зависят от операционной системы. Тем не менее, в большинстве библиотек компиляторов есть функции, выполняющие данные задачи. Приведенная здесь небольшая программа компилируется с помощью компилятора Microsoft.
/* Пример циклической очереди в качестве буфера клавиатуры. */
#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), что и в стеках.
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нем и на первый незанятый элемент.
На этом все! Теперь вы знаете все про очереди, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое очереди, очередь, циклическая очередь и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных