Page 37 - 6110

9.2.3 Організація в пам'яті комп'ютера
Стек може бути організований як масив або множина комірок в
певній області комп'ютера з додатковим зберіганням ще й
вказівника на верхівку стека. Заштовхування першого елемента в
стек збільшує адресу вказівника, виштовхування елементу зменшує
її. Таким чином, адреса вказівника завжди відповідає комірці
масиву, в якій зараз знаходиться верхівка стеку.
Багато процесорів ЕОМ мають спеціалізовані регістри, які
використовуються як вказівники на верхівку стеку, або
використовують деякі з регістрів загального вжитку для цієї
спеціальної функції в певних режимах адресації пам'яті.

9.2.4 Приклади застосування стеків
Калькулятори, які використовують зворотню нотацію,
використовують стек для збереження даних обчислень.
Існує велика кількість “стеко-орієнтованих” мов програмування
(Forth, PostScript), які використовують стек як базову структуру
даних при виконанні багатьох операцій (арифметичних, логічних,
вводу-виводу тощо).
Стеко-орієнтованими є багато з віртуальних машин, наприклад
віртуальна машина Java.
Компілятори мов програмування використовують стек для
передавання параметрів в процесі виклику підпрограм, процедур та
функцій. Спеціалізований стек використовується також для
збереження адрес повернення з підпрограм.

9.2.5 Реалізація базових алгоритмів
На високорівневих мовах програмування, стек може бути
реалізований за допомогою масиву та додаткової змінної.
Для зберігання елементів стеку резервується масив S[1..n]
певного розміру та додаткова змінна top[S], яка буде зберігати
індекс верхівки стеку.
Операції push та pop тоді можуть бути записані так (без
перевірки на переповнення та “незаповнення”):

PUSH (S, x)
1 top[S]:= top[S]+1 //збільшення індексу на 1
2 S[top[S]]:=x //запис нового елемента у верхівку стека

POP (S)
1 top[S]:=top[S]-1 // зменшення індексу на 1
2 return S[top[S]+1] //повернення колишньої верхівки стеку

36