Очередь - это упорядоченный набор элементов, в котором извлечение элементов происходит с одного его конца, а добавление новых элементов - с другого.
Очередь функционирует по принципу FIFO – first-in-first-out: «первым вошел – первым вышел».
В повседневной жизни очереди встречаются часто. Например, очередь к кассе в магазине.
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Существует несколько способов реализации очереди:
- с помощью одномерного массива; с помощью связанного списка; с помощью класса объектно-ориентированного программирования.
Основные операции с очередью:
- запись элемента в очередь (если это возможно, т. е. нет переполнения массива). чтение элемента из очереди (если очередь не пуста).
В очереди, в силу ее определения, доступны две позиции:
- ее начало (head «голова») , откуда извлекаются (обслуживаются) элементы; ее конец (tail «хвост») , куда заносятся новые элементы (ставятся в очередь на обслуживание).
Рассмотрим очередь, реализованную на одномерном массиве.
const size=8;
var a:array[0..size]of integer;
i, x,n, top:integer;
Начальное состояние: head = 0;
tail = 0;
Запись элемента: a[tail]:= x;
tail:= (tail+1) mod n;
Чтение элемента: x:=a[head];
head:= (head+1) mod n;
0 | 13 | 0 |
1 | 5 | head |
2 | 8 | |
3 | 9 | |
4 | 14 | |
5 | 5 | |
6 | tail | |
7 |
Рис. 1. Пример очереди
На рис.1 приведено состояние очереди в определенный момент времени (n = 8). Элементы записывались в очередь так: 13, 5, 8, 9, 14, начиная с нулевого элемента массива a. Чтения не было. Доступный для извлечения (обслуживания) элемент очереди – 13, он определяетсязначением указателя head. Место для записи (постановки в очередь) определяется указателем tile.
Если бы начало очереди всегда совпадало с первым элементом массива (индекс 0), то при удалении элемента из очереди потребовалось бы сдвигать все оставшиеся элементы к началу массива. Это приводило бы к неэффективности программы. Существует другой способ, при котором элементы очереди не сдвигаются – это использование «циклического массива» или «кольца». Суть этого способа заключается в том, что вычисление head и tail при чтении и записи элементов осуществляется по модулю числа n. Например, после записи в ячейку с номером 7 осуществляется запись в ячейку с индексом 0, если она, конечно свободна. Аналогично и при чтении элементов.
Замечание. Именно кольцевая очередь используется на практике, в том числе в качестве буферной памяти клавиатуры. Часто при зацикливании программ в операционных системах MS-DOS или Windows вводимые с клавиатуры и поступающие в её буфер данные не считываются из этого буфера – очередь переполняется. Индикацией этого события является звуковой сигнал.
Рассмотрим два примера:
- На рис.2а изображено состояние очереди после чтения элементов 13, 5, 8, 9, 14. Оба указателя показывают на одну и ту же ячейку (номер 5), т. е. head = tail. Это признак того, что очередь пустая. На рис.2б изображено состояние очереди, когда сначала было выполнено чтение элементов 13 и 5, а затем записаны элементы 25, 6, 9, 10, 45. Оба указателя показывают на одну и ту же ячейку (номер 2), т. е. head = tail. Это признак того, что очередь заполнена.
0 | 5 | 0 | 10 | 2 |
1 | head | 1 | 45 | head |
2 | 2 | 8 | ||
3 | 3 | 9 | ||
4 | 4 | 14 | ||
5 | 5 | 5 | 25 | 2 |
6 | tail | 6 | 6 | tile |
7 | 7 | 9 |
а) б)
Рис. 2. Очередь: a)пуста - head = tail, б)заполнена - head = tail
Имеем два неразличимых на уровне значения переменных head и tail состояния очереди. Как определить, очередь пуста (Empty) или заполнена (Full)? Для разрешения этой ситуации нужно ввести логическую переменную, например, p для фиксации факта «кто кого догнал». В первом случае, когда очередь пуста - head догнал tail ( Рис. 2а), а во втором случае, когда очередь полна – tail догнал head (Рис. 2б). Начальное значение переменной p = true, а при переходе как того, так и другого указателей (head и tail) через значение n она изменяет свое значение на противоположное. Для рассматриваемых примеров, в первом случае (Рис.2а) – p = true, а во втором (рис.2б) – p = false, так как мы уже один раз перешли через значение n (указатель tail).
Основные процедуры и функции для работы с очередью
Определение заполнена очередь или нет.
Function Queue_Full(head, tail:integer; p:boolean):boolean;
Begin if (head = tail) and not p then Queue_Full:= true
else Queue_Full:= false;
end;
2. Определение пустая очередь или нет.
Function Queue_Empty(head, tail:integer; p:boolean):boolean;
Begin if (head = tail) and p then Queue_ Empty:= true
else Queue_ Empty:= false;
end;
Запись элемента в очередь.Procedure Queue_Write( var tail:integer; var p:boolean;x:integer);
Begin a[tail]:= x;
tail:= (tail+1) mod n;
if tail = 0 then p:=not p;
end;
Чтение элемента из очереди.
Procedure Queue_Read( var head:integer; var p:boolean; var x:integer);
Begin x:=a[head];
head:= (head+1) mod n
if head = 0 then p:=not p;
end;
Существует еще одна линейная динамическая структура данных, которая называется дек.
Дек – это линейный список, в котором можно добавлять и удалять элементы как с одного, так и с другого конца.
Из определения следует, что дек может работать и как стек и как очередь.
Ссылки и материалы:
1. http://prog-cpp. ru/data-queue/
2. http://www. tdoc. ru/c/programming/pascal/turbopascal-encyclopaedia-page21.html
3. http://kvodo. ru/queue. html
4. https://www. intuit. ru/studies/courses/2193/67/lecture/1980?page=3
5. Абстрактные типы данных, БИНОМ 2009г.
6. , Информатика. Углубленный уровень. Учебник для 11 класса. Часть 2.
