6. Очередь

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

Исключение		A	B	C	D	E		Включение
						
	Начало				Конец

Очередь функционирует по принципу FIFO (First In – First Out: «первым пришел – первым исключается»). В реальном мире имеется множество примеров очередей: очередь к кассе магазина, очередь задач, обрабатываемых вычислительной машиной. Каждый элемент очереди может содержать одно или несколько полей, число элементов в очереди не ограничено. Очередь, не содержащая ни одного элемента, называется пустой.

7. Операции над очередью

Над очередью q (от англ. queue – очередь) могут быть выполнены следующие операции:

1) включение нового элемента v в конец очереди – Insert(q,v);

2) исключение элемента из начала очереди – Remove(q) и возвращение его значения;

3) выработка признака «очередь пуста» – Empty(q);

4) считывание первого элемента без его удаления – HeadValue(q);

5) считывание последнего элемента очереди – RearValue(q);

6) определение числа элементов очереди Size(q);

8) очистка очереди – Clear(q).

Первые три операции над очередью являются основными. Операции Empty, Size, и Clear для очереди аналогичны соответствующим операциям для стека.

8. Дек

Деком (DEQ – от английского double ended queue, очередь с двумя концами) называется упорядоченный набор элементов, включение и исключение элементов в котором могут осуществляться с любого из двух его концов. Логическая структура дека:

Включение Исключение	 	A	B	C	D	E	 	Исключение Включение
						
	Начало				Конец

Частные случаи дека – дек с ограниченным входом и дек с ограниченным выходом (включение или исключение элементов осуществляется только с одного из концов дека).