Лекции (984123), страница 11
Текст из файла (страница 11)
Разновидностью стека является магазин винтовки, автомата или пулемета; патроны засылаются туда в порядке., обратном последуклцей стрельбе. Таким образом, согласно известной шутке студентов ВМК, автоъ<ат Калашникова действительно является устройством для преобразования стека в очередь ~85~, с. 194. Стрелок на привале берет патроны 5.5.1 Функциональная спецификация Тип Ят или стек объектов тина, Т, характеризуется операциями ~72~; СОЗДАТЬ: ПУСТО: ГЛУБИНА: В СТГК: ИЗ СТЕКЛ: ВЕРХ: УНИЧТОЖИТЬ: Π— ' от Ят — 11гие, Га1ве1 5т- г1 Ятх Т- Ят .~т — г7т Ят- Т Ят- О За.мечаные.
Функции ВЕРХ и ИЗ СТЕКА можно обьединить в единую операцию со спецификацией .~т- Тх эт результатом которой является и элемент, и измененный стек. Для всякого элемента 1 типа Т и всякого а типа Ят имеют место следующие свойства: 1. ПУСТО(СОЗДАТЬ) — сгпе 7/ созданый стек пуст 233 из коробки: 1, 2,..., 30, заталкивая их в магазин в том жс порядке: 1, 2,..., 30.
В результате сверху оказывается 30-ый патрон, а первый патрон, конечно же, внизу, Присоединяя магазин к автомату и передергивая затвор, стрелок досылает верхний 30-ый патрон в патронник и все патроны поднимаются к верху магазина с сохранением порядка следования. При автоматической стрельбе (очередями!'1 патроны поочередно поступают в патронник из магазина и выстреливаются через ствол в порячке. обратном их закладке в магазин; 30,29,..., 1.
То есть помещение в стек инвертирует порядок следования элементов. Выходная очередь обратна входной очереди патронов, за,носимых в магазин. Отлизие магазина, от стека, ~~д~~о, с~с~о~~ и том, ~то стек имеет ~е~од~~~~~е дно и плавающую верхушку, а магазин —. фиксированную верхушку и бездонный колодец, куда в идеале можно заталкивать сколь угодно много элементов (бесконечная гостиница в фантастическом романе Ивана Ефремова «Туманность Андромеды»). Используемые на практике стеки не всегда, подчиняются классической функциональной спецификации. 'Гак, для доступа к глобальным переменным транслятору может потребоваться певерхушечное чтение (так называемое чтение по стрелке из ранее засланной в стек таблицы описаний объемлющего блока). Такой стек становится полумассивом и эффективно реализуется именно в сплошном представлении.
В связи с этим вспомним„ что стек использовался для распределения памяти для программ с вложенной блочной структурой, в том числе для организации рекурсивных вызовов. В случае необходимости быстрого возврата из глубины рекурсии, минуя промежуточные стадии, для пропуска соответствующего участка стека в стандартной библио"геке языка С!'С вЂ” -+ име1отся «нелинейные» функции работы с неявным стеком вызовов ае$рпрЦ и 1опд1шр(1. Такие функции могут бьггь реализованы для явных стеков. Заметим,что терминология стеков «вертикальная» (пачки, стопки и т. д.), в то время как очереди были нами вербализованы «горизонтально».
Более того, в ашлийском языке так и говорят: «положить на стек» и «снять со стека». В русском языке стек это магазин, и элементы «заталкивают в стек» или «извлекают из него» (851. 2. ПУСТО(В СТЕК(э, ф — Га1эе О занесение элемента в стек делает его заведомо непустым 3. ВЕРХ(В СТЕК(э, 1)) — ~ Только что занесенный в стек элемент становится его верхушкой. 4. гТ по~ ПУСТО(э) ФЬеп ВЕРХ(э); э1 .-- ИЗ СТЕКА(э); В СТЕК(эь 8) еперь; ~'* после выборки элемента из верхушки стека. с последуннцим его возвращением в стек получается исходный стек ~1' 5.
Последователыюсть действий: э: — СОЗДАТЬ э: — В СТЕК(э, ~1) э: В СТЕК~1, Ц) 1:.- ВЕРХ(э) !1 1 . 1э! э ь-- ИЗ СТЕКА~э) 1 .—.. ВЕРХ(э) П 1 . 1~! э:-- ИЗ СТЕКА(э) заносящая во вновь созданный пустой стек сначала элемент 1м а, затем элемент 12, а затем извлекающая из нее два элемента, инвертируот их гюрядок. Это свойство по инчукции может быть распространено (транзитивное замыкание) на случай любой последовательности элементов (1~, 1г,..., 1„), даже если эти элементы вставляются в непустой стек или «разбавлены» какими-то другими элементами, их строго обратный порядок на выходе из стека нарушен не будет. Замечание.
Требование непустоты стека ограничивает использование некоторых операций и свойств этих операций, блокируя соответствующие выводы из ложных посылок, но мы не стали усложнять функциональную спецификацию стека рассмотрением этих случаев. Замечание. Обратите внимание, что функциональная спецификация стека отличается от функциональной спецификации очереди только последними свойствами (ЫРО и инверсия). 5.5.2 Логическое описание Самый свежий элемент стека, т. е, последний введенный и еще не уничтоженный играет особую роль; именно его можно рассмотреть или уничтожить. Этот элемент называется верхуп|кой стека.
Оставшук)ся часть можно назвать телом стека и оно само является, по существу, стеком; если снять со стека верхушку„то тело превращается в стек. Таким образом, стек, как и очередь, является рекурсивной структурой данных и может быть описан рекурсивно как конкатенация элемента типа Т и некоторого стека э типа Ят. Для обеспечения эффективной вычислимости необходим терминатор, ограничиванпций глуоину рекурсии описания, роль которого, как в файлах и очередях, играет пу< той стек ~721: суре СТЕК-Т = (ПУСТО ! НЕПУСТОЙСТЕК) суре НЕПУСТОЙСТЕК = ( верхушка: Т; тело: СТЕК-Т) Заметим, что рекурсивность описания может бьггь не только по глубине стека, но и по сложности типа, его компонент Х: этот тип может быть произвольным, в том числе и рекурсивным, и даже стеком...
5.5.2.1 Язык программирования со стековой моделью вычислений Стек как структура данных является базовой для такого своеобразного языка п1>ог)эаммирования, как Форт. Как мы уви щм позднее, стек оказывается чрезвычайно удобным для вычисления и представления арифметических выражений. В языке Форт используется так называемая посгпфикспая (обратная пояьтая, названная так в честь Я. Лукашевича) форма записи выражений, при которой сначала записываются операнды, а затем знак операции.
Например, выражение 1 1 2 записывается как 1 2 +, а выражение 11 4 2) 4 как 1 2 + 4 ~ . В постфиксной форме порядок выполнения операций определяется исключительно их местоположением в строке; отпадает необходимость в использовании скобок и в таком понятии„как приоритет операций ~48). Главное преимущество постфиксной записи заключается в ее линейности. Обычная инфиксная форма записи нелинейна. Для вычисления представленных в постфиксной форме выражений достаточно воспользоваться следующим простым алгоритмом: встречающиеся во входной строке операнды помещаются на стек, а встречающиеся операции производятся над двумя верхними значениями со стека, с помещением результата на стек.
Таким образом, при корректной записи выражения к концу входной строки на стеке оказывается результат вычисления. Также стек идеально подходит лля передачи параметров функциям и процедурам. В языке Форт функции (как и стандартные операции +, — и др.) берут аргументы со стека и помещают результат на стек. Например, функция возведения в квадрат (которую мы обозначим ЯЦН), берет со стека один аргумент и кладет результат на стек. Пример использоьания ЯЦН в составе выражения: 110 — 3)а -1 4~ запишется как 10 3 — ЯЦН 4 ЯЦН э..
С синтаксической точки зрения ЯЦН ведет себя как одноместная постфиксная операция. Форт, как и всякая стековая машина, исполняет программу очередь ар операндов и операций в постфиксном порядке. Рассмотренная функция может быть определена через умножение следующим образом: 235 БЦВ 1П1Р ~ где: БЦВ заголовок объявления функции, ООР встроенная функция дуб||ирования вершины стека. Таким образом при выпо;п|ении функции БОК стек неявно используется и для проме; жуточных вьг|ислений: 5.5.2.2 Реализация на массиве Как и при реализации очереди на массиве ограничим максимальнук| глубину стека ве- личиной Р001. 31хбЕ.
Вес элементы стека в таком случае размс|цаются в массиве |1аСа длины Р001. 31Х16. 11сременная я1хс играет двойную роль: это длина стека, а величина я| хе — 1 является индексом его вершины. сопяС 1'ООЬ Я1ХЕ = 100; сопяС шС Р001. Б1ХЕ 100; епс1; ГппсСюп Еп|ргу(айаг я: яСас1с): Ьоо1еап Суре яСасс гесогд я1хе: шСецег: с1аСа.: аггау~О..Р001, Б1ХŠ— Ц оК Т ргосес1пге Сгеаге(айаг я: яСас1 ); Ьеиш я. я1хе:-- 0:, епс1; Ьеиш ЕшрСу:=- я.я1хе -=- 0; епс1; ГппсСюп Б1хе(айаг я; ягас1|): шСеиег; Ьеи1п Б|хе: — я.
я|хе; епс1; Сурес1еГ я СгпсС ( 1пС я1хе; Т с1аСа~Р001 Б1ХЕ]; 1 яСас1с; ъоЫ Сгеа1е(яСас~~ я) ( я — >|йхе - 0; Ьоо! ЕшрСу(я1ас1~~ я) ( геСпгп я — >|йхе — 0; шС 81хе1яСас1|* я~ ( геСпгп я — >я1хс; 1эоо! Рор(ягас1е*, я) ( 11 (! я — >я!хе) геСпгп 1а1яе; я — >я!хе — —; геСпгп Сгпс: ГппсСюп Тор(ъ~аг я: ягас1с): Т; Ьефп 11(я, я!хе гс> О) СЬеп 'Гор: — я.с!аСа !я. я!хе — 11: епе1; Т То!~(яСас!гв я) Ы1я — >в!хе) геСпгп я — >с1ага!я — >я!хе — Ц; чоЫ 1)сяСгоу(ягас!ог я) ргосее1пге 1)еяСгоу(айаг я: ягас!г); Ьеяш епд; 5.5.2.3 Реализация на динамических структурах "Гсперь опишем реализацию стека на, динамических структурах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
