    Г Л А В А 3 

    СТРУКТУРЫ ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    Эта глава посвящена реализациям одних структур данных на базе других. 
Задачи первых трех разделов формулируются такз «Пусть в языке программирования 
отсутствует способ конструирования объектов X, но имеется способ 
конструирования Y. Реализо-вать исполнителя X на базе Y». Например, 
реализовать исполнителя «Стек элементов типа Е» на базе исполнителя 

    «Вектор элементов типа Е». 

    С практической точки зрения решения таких задач интересуют нас по двум причинам. 
    .Во-первых, разбор реализаций одних структур данных на базе других 
позволяет глубже усвоить, «прочувствовать» сами эти структуры, а также 
научиться при необходимости реализовать другие структуры, не являющиеся 
предопределенными. Для математика, впрочем, вопрос о сводимости одних структур 
данных к другим может представлять и самостоятельный интерес. 
    Во-вторых, такие задачи сплошь и рядом возникают при использовании широко 
распространенных производственных языков программирования (Фортран, Си, 
разнообразные ассемблеры, Бейсик, Паскаль, Ада и др.). Из перечисленных в 
разд. 7 структур эти языки содержат только способы конструирования вектор и 
матрица (в несколько более общем виде называемом массивом). Дело в том, что 
память современных ЭВМ физически устроена как вектор эле-<; ментов некоторого 
типа с индексом от нуля до некоторого макси-"мального числа (более подробно об 
устройстве ЭВМ см. следующую главу).Именно поэтому способ конструирования 
вектор присутствует во всех языках программирования, и именно поэтому почти 
все реализации этой главы будут реализациями на базе вектора. Не следует, 
однако, думать, что на практике любая структура реализуется на базе вектора за 
один шаг декомпозиции. Часто приходится сделать несколько шагов, используя 
промежуточные структуры данных, прежде чем искомая структура окажется 
реализованной на базе вектора. Практический пример такой многошаговой 
реализации приведен в разд. 18. 
    При решении задач иногда возникает необходимость в использовании и 
нестандартных структур, формы работы с элементами которых специфичны для 
каждой конкретной задачи, Примерам таких 

    J90	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ   И  ИХ  РЕАЛИЗАЦИИ 

    структур и методам их реализации посвящены разд. 16—18. Начиная с этих 
разделов, на наших страницах начнет появляться аббре-„натура ЭВМ — 
электронно-вычислительная машина. Включение информации об ЭВМ в курс 
программирования вызвано тем, что на практике именно ЭВМ лежат в основе тех 
реальных Универсальных Вынолнителей, которые выполняют наши, программы. Тем 
самым программисту полезно знать общее устройство и принцип работы, алгоритмы 
функционирования отдельных компонент и другие детали конструкции ЭВМ. Этим 
вопросам будет посвящена следующая глава. Здесь же, занимаясь вопросами 
реализации различных структур данных, мы будем объяснять некоторые детали 
устройства ЭВМ, чтобы показать, откуда возникает та или иная структура, та или иная 
задача. 
    С теоретической точки зрения глава описывает некоторые новые структуры 
данных (файловая система, виртуальная память), а ее основное содержание 
составляют общие методы и конкретные приемы реализации различных структур 
данных на базе вектора: не-прерывные реализации, ссылочные реализации, 
бинарный поиск, хеширование и т, д. 

    12   Примеры реализации одних структур данных на базе других. Непрерывные 
реализации на базе вектора 

    Последовательность на базе двух очередей. Рассмотрим задачу реализации 
исполнителя «Последовательность элементов типа Е> на базе двух исполнителей 
тина «Очередь элементов типа Е». Другими словами   надо написать программы, 
соответствующие предписаниям исполнителя «Последовательность», которые будут 
«создавать видимость»  работы  с  последовательностью,  в  то  время  как  на  
самом деле будут манипулировать двумя очередями. Этот факт надо постоянно 
иметь в виду-во всех реализациях и здесь и далее всегда будут имитируемая 
структура и структуры, с которыми мы па самом деле работаем. На идейном уровне 
решение таких задач состоит в том, что надо придумать размещение элементов 
имитируемой  (или воображаемой)  структуры в реальной и понять, к каким 
реальным   действиям   будут   приводить   операции   с   воображаемой 
структурой. Первую часть задачи — размещение элементов - удобно придумывать и 
изображать на картинках (рис. 12.1). 
    На рис. 12.1 элементы воображаемой структуры «Последовательность» 
изображены кружками и расположены в двух очередях (левая и правая «трубы» 
соответственно). При этом элементы во-отражаемой прочитанной части 
последовательности расположены в „чевой очереди, а элементы воображаемой 
непрочитанной части-в ufsавоа очереди, 

    12.   НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА 191 

    Когда такая картинка придумана, надо просмотреть систему предписаний 
имитируемого исполнителя (исполнителя «Последовательность») и убедиться в том, 
что выбранный порядок размещения элементов позволяет проимитировать все 
операции с этим исполнителем. В данном случае это действительно так. Например, 
имитация предписания «прочесть очередной элемент последовательности в <вых : 
Е> состоит в том, что надо взять элемент из начала правой очереди, добавить 
его в конец левой очереди (т. е. в прочитанную часть последовательности), а 
также скопировать состояние этого элемента в выходной параметр Е. 
    Отметим, что число реальных действий с очередями, выполняемых при имитации 
этого предписания, невелико и не зависит JM^ 

    прочитанная часть 
    О О О О 
    Последовательность 
    непрочитанная часть 
    О О О О О 
    начало •«S
    -кснец       паче/то 
    Левая очередь <ЛО>	Правая очередь (ПО) 

    Рис. 12.1 

    числа элементов, в последовательности или в очередях. В реализации 
последовательности это свойство (назовем его отсутствием мас-^^ совых 
операций) будет выполнено для всех предписаний, кроме предписания «"встать в 
начало последовательности», когда число действий зависит от количества 
элементов имитируемой последователь, нести. Допустима или нет такая медленная 
имитация этого пред* нисания, зависит от ситуации, в которой мы собираемся 
использовать мосл1'до]|;1Т1М1Ы1О1ТЬ. 
    Идеи   имитации  остальных   предписаний  исполнителя  
«Последо-вательность» ясны из текста реализации. 
    исполнитель Последовательность | (на базе двух очередей) .СП: 
    1. начать работу 
    . 2. сделать последовательность пустой . 3. последовательность пуста	: да/нет 
    4. добавить элемент (вх: Е) в конец последовательности 
    . 5. встать в начало последовательности 
    , 6. есть непрочитанные элементы	: да/нет 
    . 7. нет непрочитанных элементов                  : да/нет 
    .- 8. ирочесть очередной элемент в (вых: Е) 
    . 9. очередной элемент последовательности:           ; :Е ( 
    10. пропустить очередной элемент последовательности 


    192	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ   И  ИХ  РЕАЛИЗАЦИИ .   


    11. кончить работу 

    . идеи реализации: 

    Последовательность будем хранить в левой (ЛО) и правой (ПО) очередях. 
Левая очередь будет соответствовать прочитанной части последовательности, а 
правая — непрочитанной: 
    Последовательность 
    прочитанная часть 
    непрочитанная часть 
    начало    (________    конец 
    Левая очередь (ЛО) 
    начало     {________      коней 
    Правая очередь (ПО) 
    . используемые исполнители: 
    ЛО, ПО:очередь элементов  типа Е 
    конец описаний | ________________________________ 
    программа начать работу == ЛО.начать работу; ПО.начать работу программа 
сделать последовательность пустой = = 
    ЛО.сделать очередь пустой; ПО.сделать очередь пустой программа 
последовательность пуста:да/нет == 
    (ЛО.очередь пуста и ПО.очередь пуста) 
    программа добавить элемент (вх : Е) в конец последовательности = = ПО. 
добавить элемент (вх: Е) в конец очереди 
    программа встать в начало последовательности 
    . дано : | последовательность как-то расположена в 2 очередях . получить: 
| последовательность целиком в правой очереди, т. е. .	ЛО.очередь пуста """"~" 
    .    цикл V Е е очереди ПО выполнять 
    ЛО.добавить элемент (вх: Е) в конец очереди .    конец цикла .        утв: 
ПО.очередь пуста .    цикл V Е е очереди ЛО выполнять 
    ПО.добавить элемент (вх: Е} в конец очереди .    конец цикла 
    утв: ЛО.очередь пуста конец программы 
    программа есть непрочитанные элементы : да/нет == 
    ПО.очередь не пуста программа нет непрочитанных элементов : да/нет == 
    ПО.очередь пуста 


    12,   НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА 193 


    программа прочесть очередной элемент в (вых: Е) . дано        : есть 
непрочитанные элементы . получить: 
    ,    ПО.взять элемент из начала очереди в (вых : Е) 
    .    ЛО. добавить элемент (вх: Е) в конец очереди 
    конец программы ^^в*»**" /программа очередной элемент последовательности 
:: Е 
    . дано        : есть непрочитанные элементы 
    . получить: 
    .   ответ == ПО. начало очереди	* конец программы 
    "Программа пропустить очередной элемент последовательности . дано        : 
есть непрочитанные элементы . получить: 
    ,   ПО.взять элемент из начала очереди в (вых:Е) .    ЛО.добавить элемент 
(вх:Е) в конец очереди конец программы 
    программа кончить работу == 
    ЛО.кончить работу: ПО.кончить работу конец исполнителя | = = » = -=.=.-=, 
= = =i^s= = = = = = =, = =.---. = ---=. 
    Здесь мы впервые встречаемся с программной реализацией предписания, 
принимающего и вырабатывающего значение. Такое предписание является 
обозначением для некоторого глобального объекта, в данном случае — объекта 
«ПО.начало очереди». Обратите внимание на форму записи ответа в таких 
программах — вместо ответ: = пишется ответ==, причем справа от знака 
    =>= (читаете* «это есть») может стоять только некоторый глобальный объект 
или его обозначение. Таким образом, запись " 
    Последовательность.очередной элемент ;= 7 означает то же самое, что и 
ПО.начало очереди : = 7, и  означает,  что  элемент,  находящийся  в  начале  
правой  очереди, должен быть установлен в состояние 7. Аналогично запись 
    х := х + Последовательность.очередной элемент означает то же самое, что и 
    х : = х + ПО.начало очереди, 


    7     А, Г, Кушниренко, Г. В. Лебедев 
    194 . 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 

    При использовании реализованного выше исполнителя «После" довательность» 
можно отвлечься от реализации и считать (воображать), что этот исполнитель 
действительно содержит последовательность элементов типа Е. Повторим, однако, 
что при реализации втого исполнителя мы на самом деле манипулируем двумя 
очередями, лишь имитируя соответствующие действия с последовательностью. 
    Непрерывные  реализации  на  базе вектора.  Теперь рассмотрим задачу 
реализации различных структур   (стек, дек, очередь и т. п.) элементов  типа  
Е  на   базе  вектора  элементов  типа  Е.  Поскольку число  элементов   
вектора   заранее   фиксировано   и   конечно,   то  на базе   вектора   можно 
реализовать   лишь   ограниченные   стек,   дек, очередь и пр. Ограниченная 
структура отличается от потенциально неограниченной тем, что может вместить не 
более некоторого, заранее фиксированного числа элементов. При попытке добавить 
элемент сверх этого числа   (при  «переполнении»)   возникает ситуация 
«отказ». Система предписаний ограниченной структуры кроме обычных содержит 
также предписания есть свободное место/нет свободного места     ! да/нет Эти 
предписания  проверяют, является  ли уже количество  элементов структуры 
максимальным  (нет свободного места)  или еще нет (свободное место есть). 
    Будем называть простыми объекты предопределенных типов (да/нет, символ, 
Z+, Z, R), а также объекты, построенные с помощью способов конструирования 
перечисление и отрезок. Во всех реализациях на базе вектора предполагается, 
что кроме самого вектора можно использовать произвольное число объектов 
простых типов, а также записей из'них. Единственное требование состоит в том, 
чтобы количество таких об"ъектов ^2_за_вдсело от количества элементов в 'векторёГ" 
    ' В' этом разделе мы изучим только один метод реализации структур на базе 
вектора, который называется непрерывной реализацией. Суть этого метода состоит 
в том, что элементы структуры размещаются в векторе «непрерывным куском» — 
рядом друг с другом, а порядок элементов в структуре, если он есть, 
определяется поряд*-ком их следования в векторе. 
    Ограниченный стек на базе вектора. При реализации ограниченного стека на 
базе вектора расположим элементы имитируемого стека в начале вектора (рис. 
12.2). В изображенной на рис. 12.2 ситуации воображаемый стек содержит шесть 
элементов. Вершина стека находится в компоненте вектора с индексом 6, 
следующий за ней элемент — в компоненте вектора с индексом 5 и т. д. Дно стека 
находится в компоненте вектора с индексом 1, Тем самым шесть 

    12.   НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА 195 

    элементов воображаемого стека действительно хранятся в вектора 
«непрерывным куском», занимая элементы вектора с индексами от 1 до 6. 
Состояния элементов вектора с индексами, большими 6, в этот момент не важны •» 
они никак не влияют на имитацию стека. 

    ЛНО 
    Стек 
    вершина 
    lob	0	о	0	0	1		... 
    123456787                             П-ЛП вектор элементов типа Е с 
индексом типа 1..П 

    Рис.   12.2 

    Естественно, что для имитации работы со стеком недостаточно хранить 
состояния элементов вектора — нужно знать еще и числа элементов в стеке. Для 
хранения этого числа достаточно объекта 

    мощность :0. .п   | число элементов в стеке 
    исполнитель Ограниченный стек [ на базе вектора . СП: 
    .     1. начать работу 
    «     2. сделать стек пустым 
    .    3. стек пуст	: да/нет 
    1    4. есть свободное место	: да/нет 
    .    5. нет свободного места	: да/нет 
    •    С. добавить элемент (вх: Е) в стек i    7. взять элемент из стека в 
(вых! Е) 
    •    8. вершина стека	I: Е «    1). удалить iicpuiHiiy стека 
    •    10.  кончим,  работу 
    >• 
    . константы: 
    ,   максинд=100 | макс.индекс, т. е. число элементов вектора 
    • 
    . объекты: 
    ,    мощность : 0. .максинд | т. е. число элементов в стека 
    • 
    i идеи реализации! 
    • Расположим элементы стека в начале вектора, "повернув" стек « дном к 
началу вектора. В стеке из трех элементов, таким обра-, зом, вершина стека 
будет в 3 компоненте вектора, следующий . за вершиной элемент — во 2, а дно 
стека — в 1, используемые исполнители! 

    196	' ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И ИХ  РЕАЛИЗАЦИИ 

    .   вектор:вектор элементов типа Е с индексом )..максинд 
    конец описаний 

    программа начать работу == вектор.начать работу; мощность : программа 
сделать стек пустым	=«== мощность: = О программа стек пуст                     
 : да/нет == мощность =0 программа есть свободное место : да/нет == мощность  
< максинд программа нет свободного места : да/нет == мощность = максинд 
    программа добавить элемент (вх: Е) в стек . дано        : есть свободное 
место . получить: 
    .    мощность.увеличить на 1 .    вектор (мощность) := Е конец программы 
    программа взять элемент из стека в (вых: Е) , дано        : стек не пуст . получить: 
    .    Е :•= вершина стека *  удалить вершину стека конец программы 
    программа вершина стека :: Е .дано        : стек не пуст . получить: 
    . ответ == вектор (мощность) конец программы 
    программа удалить вершину стека . дано        : стек не пуст . получить: 
    мощность.уменьшить на 1 конец программы 
    программа кончить работу == вектор, кончить работу конец исполнителя 
   | = = = „ = = = = = = = = = = = „-- = = = = 

    Ограниченная очередь на базе «циклического» вектора. Следую» щей задачей 
является реализация ограниченной очереди на база «циклического» вектора. Это 
название, впрочем, не вполне верно —• вектор здесь используется самый обычный, 
а слово «циклический» 

    12,    НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА 197 

    относится к идеям реализации. Дело в том, что если как-то распо< ложить 
элементы очереди в непрерывном куске вектора, а потом начать добавлять 
элементы в конец и брать из начала, то в некоторый момент времени очередь 
«упрется» в правый край вектора 
    Очередь начало      коней 

    345    6789	П-1 вектор элементов типа Е с индексом типа t..n 

    • •	О	о 




    Рис. 12.3 
    •	• 

    '(рис. 12.3). В этот момент для добавления очередного элемента в конец 
очереди, вообще говоря, надо сдвинуть все элементы очереди влево по вектору, 
чтобы справа освободилось место. Количество элементарных операций с вектором, 
которые придется проделать при сдвиге, пропорционально числу элементов в 
очереди. Таких массовых (т. е. зависящих от числа элементов имитируемой структуры) 
действий можно избежать, если «свернуть вектор в кольцо» (рис. 12.4), т. е. считать, 
что за последним элементом вектора идет нериын. Тогда, «упершись» в правый край 
вектора, надо по кольцу 

    конец 

    Рис.   12.4 

    перейти к первому элементу вектора, затем ко второму и т. д. Поскольку при 
этом элементы очереди на кольце размещаются непрерывным куском, то такая 
реализация также называется непрерывной. Таким образом, под словом 
«непрерывность» надо теперь понимать непрерывность на кольце. В 
программировании непрерывную реализацию очереди на базе «циклического» (т. е. 
свернутого и кольцо) вектора часто называют кольцевым буфером. 
    Посмотрим, какие еще объекты, кроме вектора, необходимы для имитации 
очереди. Прежде всего надо знать, где именно в векторе ,(нли, что то же самое, 
на кольце) расположены элементы воображаемой очереди, т. е. знать, где 
находится начало очереди и куда 

    198 ГЛ. 3. СТРУКТУРЫ ДАННЫХ И ИХ РЕАЛИЗАЦИИ 

    помещать элементы, добавляемые в конец. Будем хранить соотч ветствующую 
информацию в объектах 
    начало, конец : индекс   | индексы начала и конца очереди 
    Возникает, правда, вопрос: каковы будут состояния этих объектов в пустой 
очереди? В одноэлементной очереди «начало» и «конец» совпадают и показывают на 
единственный элемент очереди '([рис. 12.5,а). При взятии элемента из начала 
очереди объект «начало» обычно продвигается вперед (против часовой стрелки) по 
кольцу. Естественно поэтому считать, что в 
    пустой очереди «начало» 
    начала 
    конец 
    конец 
    показывает на элемент, следующий за элементом, на который указывает 
«конец» (рис. 12.5,6). Однако в точно таком же положении объекты «начало» и 
«конец» должны быть, если очередь занимает весь вектор целиком (рис. 12,5, в). 
    Таким образом, чтобы отличить пустую очередь от полной, объектов «начало» 
и «конец» мало. Не мудрствуя лукаво, введем еще один объект 
    мощность : 0. .максинд   |т  е. число элементов в очереди 
    который будем использовать для определения пустоты или непустоты очереди, 
а также наличия или отсутствия свободного места в точности так, как 
использовали объект «мощность» при реализации стека. 
    исполнитель Ограниченная очередь | на базе "циклического" вектора . СП: 
    1. начать работу ,    2. сделать очередь пустой .    3. очередь пуста	: да/нет 
    4. есть свободное место	: да/нет 
    5. нет свободного места	: да/нет .    6. добавить элемент (вх: Е) в конец, очереди 

    12.   НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА	199 

    .    7. взять элемент нз начала очереди в (вых: Е) 
    8. начало очереди	;; Е .    9. удачить начало очереди 
    .   — следующий индекс (вх: индекс)	; индекс .   10. кончить работу 
    * 
    .	константы: 
    .	максинд =100 | макс.индекс, т. е. число элементов вектора 
    .	типы: 
    .	индекс = 1.. максинд 
    .	объекты: 
    .	мощность :0..максинд |т. е. число элементов в очереди 
    .	начало, конец: индекс | индексы начала и конца очереди 
    . идеи реализации) 
    ., "Склеим" концы вектора и будем реализовывать очередь на гтп. . 
лучившемся кольце. Элементы очереди будем хранить в комио-. нентах вектора с 
индексами начало..конец 
    . используемые исполнители: 
    .    вектор : вектор элементов типа Е с индексом типа индекс 
    конец описании | -_ ——— — — _ — _________________ 
    программа начать работу ==» 
    вектор.начать работу; сделать очередь пустой программа сделать очередь 
пустой . дано        : . получить: очередь пуста 
    .    конец        !•• мяксипд 
    .    титло      :• следующий индекс (конец) 
    мощность :«= 0	,      ,;';..' конец программы 
    программа очередь пуста	«да/нет == (мощность ==0) программа есть свободное 
место : да/нет == (мощность < максннд) И|мм|1пмма нет свободного места : 
да/нет == (мощность = максинд) 
    программа добавить элемент (вх: Е) в конец очереди , дано        : есть 
свободное место . получить: 
    .    конец := следующий индекс (конец) .    вектор (конец) := Е .    
мощность.увеличить на I конец программы 

    200	гл> 3. СТРУКТУРЫ  ДАННЫХ   И   ИХ   РЕАЛИЗАЦИИ 

    программа взять элемент из начала очереди в (вых: Е) . дано        : 
очередь не пуста . получить: 
    .    Е := начало очереди .    удалить начало очереди конец программы 
    программа начало очереди :: Е . дано        : очередь не пуста . получить: 
    .    ответ == вектор (начало) конец программы 
    программа удалить начало очереди . дано        : очередь не пуста . получить: 
    .    начало := следующий индекс (начало) .    мощность.уменьшить на 1 
конец программы 
    программа следующий индекс (вх: И: индекс): индекс . дано        :   И : 
индекс ] индекс некоторого элемента вектора . получить: | индекс следующего 
элемента вектора.   Следующим за | последним считается первый элемент 
    . выбор 
    . .    при И < максинд =»• ответ := И + 1 
    ..    при И = максинд **• ответ := 1 
    . конец выбора 
    конец программы 
    программа кончить работу -- вектор. кончить работу 
    конец исполнителя |--------- = •»=- = = «=>«•----•• 
    Заметьте, что программу «следующий индекс» можно записать короче, если 
использовать операцию mod, которая получает остаток от деления первого 
аргумента на второй: 
    программа следующий индекс (вх : И : индекс): индекс -
    (И mod максинд) + 1 
    ЗАДАЧИ И УПРАЖНЕНИЯ	.? 
    В задачах 1—13 требуется реализовать одну структуру, состоящую из 
элементов типа Е, на базе другой структуры, также состоящей из элементов типа 
Е, Если в задаче фигурирует вектор 
    12.   НЕПРЕРЫВНЫЕ   РЕАЛИЗАЦИИ   НА   БАЗЕ   ВЕКТОРА 201 
    '(задачи 8 и 9), то это вектор элементов типа Е с индексом типа 1 . . 
максинд, где максинд ^1 — некоторое целое число. Кроме базовой структуры в 
реализации разрешается использовать любое ко« личество объектов простых типов 
и записей из них. 
    1. Последовательность на базе динамического вектора, 
    2. Динамический вектор на базе последовательности, 
    3. Стек на базе Л 1 -списка. 
    4. Дек на базе Л2-списка. 
    5. Очередь на базе Л 1 -списка. 
    6. Очередь на базе Л2-списка. 
    7. Множество на базе Л 1 -списка. 
    8. Вектор на базе динамического вектора. 
    9. Вектор на базе последовательности. 
    10. Динамический вектор на базе нагруженного множества. '|   11. Л 1 
-список на бале дека. .    12. Два стека на базе Л2-списка. 13. Л2-СПИСОК на 
базе двух стеков. 
    Указание. Два стека — это исполнитель со следующей си. стемой предписаний: 
    1. начать работу 
    2. г долить стек <вх : N) пустым 
    3. стек <вх : N) пуст/стек <вх : N) не пуст 
    4. добавить элемент <вх : Е> в стек <вх : N> Б. взять элемент из стека <вх 
: N> в <вых : Е> 
    6. вершина стека <вх : N> 
    7. удалить вершину стека <вх : N> 
    8. кончить работу 
    да/нет 
    :E 
    ГД1  входной  ииримпр  N,  принимающий  одно из двух значений  | или  Э,  
имеет  смысл  номера  стека,  к  которому  относится  предпи* 
    (II МНС. 
    И задачах 14 — 18 надо провести непрерывную реализацию ука-минных 
исполнителей на базе одного вектора элементов' типа Е г индексом типа 1 . , 
максинд, где максинд ^1 — некоторое целое мнгли. Кроме вектора разрешается 
использовать любое количество ППЬРКТОИ простых типов и записей из них. 
    14. Ограниченное множество элементов типа Е, 
    15. Ограниченный дек элементов типа Е. 
    16. Ограниченную  последовательность  элементов  типа   Е. 
    17. Ограниченный динамический вектор элементов типа  Е, 
    18. Два стека элементов типа Е, ограниченные в совокупности. (Система 
предписаний исполнителя «Два стека» приведена в ука-•ли ни к задачам 12 и 13. 
Слова «ограниченные в совокупности», что ограничено лишь суммарное количество элементов 

    202 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И   ИХ   РЕАЛИЗАЦИИ 

    S3. ССЙЛОЧНЫЕ РЕАЛИЗАЦИИ НА БАЗЕ ВЕКТОРА 203 
    /01 

    в обоих стеках. Таким образом, предписание «есть свободное место» является 
общим для обоих стеков и не имеет параметра, указывающего номер стека.) 
    19. Реализуйте матрицу элементов типа Е с индексами типа (1 ,. М, 1, .. N) 
на базе вектора элементов типа Е с индексом типа 1 ., максинд, где максинд =-М 
* N." 