Очередь, стек, дек

Всем перечисленным структурам свойственна операция "выборка" (чтение с удалением).

Очередью называется структура данных, добавление записи в которую производится в конец цепочки, а выборка осуществляется из начала цепочки. Очередь работает по принципу

FIFO (First-In, First-Out) – поступивший первым, обслуживается первым.

Стеком называется структура данных, добавление записи в которую и выборка записи из которой производится из начала цепочки (вершины стека). Стек работает по принципу LIFO (Last-In, First-Out) – поступивший последним, обслуживается первым.

Деком называется структура данных, у которой добавление и выборка записей осуществляется как в начале, так и в конце цепочки. Дек является обобщением структур данных очередь и стек.

Логические описания.

Пусть записи принадлежат типу Inf; S - стек; S' - непустой стек; О - очередь; О'- непустая очередь.

Тогда можно определить стек и очередь следующим образом:

Стек

S=(пусто¦S');

S'=(i:Inf,s:S)

Oчередь

О=(пусто¦О');

О'=(i:Inf,o:O¦o:O,i:Inf).

Это рекурсивные определения структур стек и очередь. Рекурсивное определение предполагает использование рекурсивных алгоритмов при реализации операций.

Операции над деком включают все операции, перечисленные в таблице, учитывая, что S и O есть частные случаи дека.