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

   A1) Null ( Create ) = true ;
   A2) Null ( Postfix ( q , p ) ) = false ;
   A3) First ( Postfix ( q , p ) ) = if Null ( q ) then p else First ( q ) ;
   A4) Rest ( Postfix ( q , p ) ) = if Null ( q ) then Create
                                    else Postfix ( Rest ( q ) , p ).
   В качестве примера использования базовых функций при операциях над
очередью дадим определение функции сцепления двух очередей q1 и q2:

    Concat ( q1 , q2 ) ≡ if Null ( q1 ) then q2 else if Null ( q2 ) then q1
                     else {not Null ( q1 ) & not Null ( q2 )}
                     Concat ( Postfix ( q1 , First ( q2 ) ) , Rest ( q2 ) )


                          2.2. Реализация стека и очереди

   Ссылочная реализация стека и очереди в динамической памяти в основном
аналогична ссылочной реализации линейных списков, подробно рассмотрен-
ной в 1.3. Упрощение здесь связано с отсутствием необходимости работать с
текущим (“внутренним”) элементом списка. Идеи такой реализации ясны из
рис. 2.1.

  Стек:


                                      Верхушка стека

  Очередь:
             Начало:

              Конец:

                       Рис. 2.1. Ссылочное представление стека и очереди

    Для ссылочной реализации дека естественно использовать Л2-список
(см.1.5).
    Поскольку для стека, очереди и дека доступ к элементам осуществляется
только через начало и конец последовательности, то эти структуры данных
допускают эффективную непрерывную реализацию на базе вектора (в отличие
от Л1- и Л2-списков, см.1.1, с.4).
    При непрерывной реализации ограниченного стека на базе вектора для
представления стека используется одномерный массив (вектор) Mem: array
[ 1 .. n ] of α и переменная Верх: 1 .. n (рис. 2.2).




                                            38