Стек - магазинный тип
Cтраница 2
Очередность, в которой производится обработка подфайлов, не препятствует корректному выполнению алгоритма быстрой сортировки и не приводит к увеличению времени выполнения сортировки, однако может повлиять на размеры стека магазинного типа, положенного в основу рекурсивной структуры. В рассматриваемом случае первым обработке подвергается меньший из подфайлов, образованных в результате каждого разделения. [16]
То, что в реализациях на базе массива и связного списка элементы стека хранятся в разном порядке, для клиентских программ не имеет никакого значения. В реализациях могут использоваться какие угодно структуры данных, лишь бы они создавали впечатление абстрактного стека магазинного типа. В обоих случаях реализации способны создавать впечатление эффективного абстрактного объекта, который может выполнять необходимые операции с помощью всего лишь нескольких машинных инструкций. [17]
Примером такого языка является язык PostScript. Это завершенный язык программирования, в котором программы пишутся в постфиксном виде и интерпретируются с помощью внутреннего стека, точно как в программе 4.5. Хотя мы не можем осветить здесь все аспекты этого языка ( см. раздел ссылок), он достаточно прост и мы можем изучить некоторые реальные программы, чтобы оценить полезность постфиксной записи и абстракции стека магазинного типа. [18]
Выполнение операции затолкнуть означает запоминание элемента в позиции массива, указываемой индексом верхушки стека, а затем увеличение этого индекса на единицу; выполнение операции вытолкнуть означает уменьшение индекса на единицу и извлечение элемента, обозначенного этим индексом. Операция создать ( конструктор) осуществляет размещение массива указанного размера, а операция проверить, пуст ли стек проверяет, не равен ли индекс нулю. Скомпилированная вместе с клиентской программой ( такой, как программа 4.5 или 4.6), эта реализация обеспечивает рациональный и эффективный стек магазинного типа. [19]
 |
Структура памяти набора символов. [20] |
Когда редактор VECED выделяет сегменты для записи образа символа, он, как было сказано выше, определяет их номера с помощью указателя сегмента. Это справедливо ТОЛЬКО в том случае, когда в памяти НЕТ освобожденных сегментов. Если же они есть, то образ символа записывается прежде всего в освобожденные сегменты памяти, номера которых выбираются из стека сегментов. В соответствии с рис. 11.7 и рис. 11.8 этот стек представляет собой стек магазинного типа. Это значит, что последний освобожденный сегмент используется первым. Процесс организован следующим образом. [21]
Страницы: 1 2