Динамические структуры данных. Алексеев А.Ю - 36 стр.

                                 2. СТЕКИ И ОЧЕРЕДИ


                         2.1. Спецификация стека и очереди

    Ранее в 1.2 и 1.5 при задании спецификации линейных списков использо-
валась абстракция (модель) последовательности. При этом были определены
функции над последовательностями First, Last, Rest, Lead, Prefix и Postfix. На-
помним эти определения, сохранив те же обозначения, что и ранее, и допол-
нительно обозначив тип последовательности w = [ x1 , x2 , ... , xn ] из элементов
xi типа El как Sequence ( El ). Функции First, Last, Rest, Lead определены толь-
ко для непустых последовательностей ( w ≠ ∆ ):

   First: Sequence ( El ) → El;                         First ( w ) = x1;
   Last: Sequence ( El ) → El;                          Last ( w ) = xn;
   Rest: Sequence ( El ) → Sequence ( El );             Rest ( w ) = [ x2 , ... , xn ];
   Lead: Sequence ( El ) → Sequence ( El );             Lead ( w ) = [ x1 , x2 , ... , xn-1 ].

   Функции Prefix и Postfix определены для любых последовательностей:

             Prefix: El ⊗ Sequence ( El ) → Sequence ( El );
             Postfix: Sequence ( El ) ⊗ El → Sequence ( El );
   Prefix ( x0 , w ) = [ x0 , x1 , x2 , ... , xn ]; Postfix ( w , x ) = [ x1 , x2 , ... , xn , x ].

   Таким образом, набор функций First, Rest, Prefix, Last, Lead, Postfix обес-
печивает доступ к элементам последовательности (“чтение”элементов из по-
следовательности и дописывание элементов в последовательность) только че-
рез ее начало и ее конец. Последовательность может рассматриваться как
самостоятельная структура данных. Тогда функции First, Rest, Last, Lead - се-
лекторы, а функции Prefix и Postfix - конструкторы типа Sequence ( El ). Более
того, используя разные подмножества набора базовых функций этой структу-
ры, получают различные полезные структуры данных. Так, если ограничиться
только функциями First, Rest, Prefix (или только функциями Last, Lead,
Postfix), то получается структура данных, известная как стек (или магазин).
Рассмотрение только функций First, Rest, Postfix (или только Last, Lead, Prefix)
соответствует структуре данных очередь (англ. queue). Если же используют
весь набор функций, то соответствующую структуру данных обычно называ-
ют дек (от англ. deq - аббревиатуры сочетания double-ended-queue, т.е. “оче-
редь с двумя концами”). Во всех этих структурах данных необходимо доба-
вить еще две функции: 1) предикат-индикатор Null : Sequence ( El ) → Boolean,

                                                36