Стек - магазинный тип
Cтраница 1
Стек магазинного типа представляет собой идеальный механизм для сохранения промежуточных результатов таких вычислений. [1]
Определение 4.2 Стек магазинного типа - это АТД, который включает две основные операции: вставить, или затолкнуть ( push) новый элемент и удалить, или вытолкнуть ( pop) элемент, вставленный последним. [2]
Напишите реализацию стека магазинного типа на базе связного списка, в которой элементы списка хранятся начиная с первого занесенного элемента и завершая последним занесенным элементом. [3]
Измените реализацию стека магазинного типа на базе массива ( программа 4.7) так, чтобы она вызывала функцию-член еггог (), если клиентская программа пытается выполнить операцию вытолкнуть, когда стек пуст, или операцию затолкнуть, когда стек переполнен. [4]
Постфиксная запись и стек магазинного типа обеспечивают естественный способ организации ряда вычислительных процедур. В некоторых калькуляторах и языках программирования метод вычислений явно базируется на постфиксной записи и стековых операциях - при выполнении любой операции ее аргументы извлекаются из стека, а результат возвращается в стек. [5]
В этой реализации стека магазинного типа предполагается, что класс Item имеет тип int, который возвращает целые числа в диапазоне от 0 до maxN - 1, так что он может поддерживать массив t, где каждому элементу стека соответствует отличное от нуля значение. Этот массив дает возможность функции push быстро проверять, не находится ли уже в стеке ее аргумент, и если так, то не предпринимать никаких действий. В каждом элементе массива t используется только один бит, поэтому при желании можно сэкономить оперативную память, используя вместо целых чисел символы или биты ( см. упр. [6]
Поскольку в программе использован стек магазинного типа, его указатель после выбора номера сегмента уменьшается на единицу, и подпрограмма завершается. Имейте в виду, что если вы редактируете уже существующий символ набора и вносимые изменения не столь велики, то при записи в память его образ будет располагаться в тех же физических сегментах, что и исходный символ. Поэтому многократное незначительное редактирование символов не будет приводить к тому, что физические сегменты символов окажутся хаотически разбросанными по всему полю памяти набора. Рассмотрим это более подробно. [7]
Этот интерфейс идентичен интерфейсу стека магазинного типа из программы 4.4, за исключением имен функций. Эти два АТД отличаются только спецификациями, что совершенно не отражается на коде интерфейса. [8]
 |
Структурная схема КР580ВГ75. [9] |
В микросхеме есть два стека обратного магазинного типа емкостью 16 знаков по 7 бит каждый. Стеки попарно сопряжены с буферными ЗУ и служат для увеличения их емкости в прозрачном режиме. [10]
Напишите программу, которая с использованием стека магазинного типа преобразует постфиксное выражение в инфиксное. [11]
Предположим, что вы изменяете интерфейс стека магазинного типа, заменяя операцию проверить, пуст или стек операцией подсчитать, которая возвращает количество элементов, находящихся в данный момент в структуре данных. [12]
Представленная ниже нерекурсивная реализация ( см. главу 5) использует явно определенный стек магазинного типа, заменяя рекурсивные вызовы помещением в стек параметров, а вызовы процедур и выходы из них - циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. [13]
Так же как и в главе 3, для выполнения быстрой сортировки можно воспользоваться стеком магазинного типа, рассматривая его как стек, в котором в виде сортируемых подфайлов содержится перечень работ, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подфайла, он выталкивается из стека. После разделения файла получаются два подфайла, требующих дальнейшей обработки, которые и заталкиваются в стек. В рекурсивной реализации, представленной программой 7.1, стек, который поддерживается системой, содержит именно эту информацию. [14]
В данном контексте наш интерес к языку PostScript объясняется тем, что этот широко используемый язык программирования базируется на абстракции стека магазинного типа. Действительно, в аппаратных средствах многих компьютеров реализованы основные стековые операции, поскольку они являются естественным воплощением механизма вызова функций: при входе в процедуру текущее состояние программной среды сохраняется путем занесения информации в стек; при выходе из процедуры состояние программной среды восстанавливается за счет извлечения информации из стека. Как будет показано в главе 5, эта связь между магазинными стеками и программами, которые организованы в виде функций, обращающихся к другим функциям, отражает важную модель вычислительного процесса. [15]
Страницы: 1 2