МЕНЮ
Гостевая книга
Форум
КАК ОРГАНИЗОВАТЬ СТЕК
Перво-наперво разберемся, а что же такое стек? Стек это такая гипотетическая структура, которую можно объяснить на примере.
Пример: Все знают, как выглядит штанга. На
нее одеваются блины. Но когда штангу не поднимают - блины надо куда-то
ложить. Для этого есть специальные держатели - типа штырей, торчащих
вверх. На них одевают диски. Главное - что если мы положили туда диски
весом 1,2,5,10 и 20 килограмм, то первым снимется какой? Конечно 20
килограмм - который мы положили последним. Ведь остальные ПОД ним.
Вторым снимется 10 килограмм и так далее. Или - более кратко -
первым снимается тот, который положили последним. По английски это
кратко зовется "LIFO", что означает "последний пришел - первый вышел"
Представим себе стек, куда положили значения 3,4,5:
Когда мы положили в стек 3 - это число было там одно. Потом мы положили
туда четыре - оно закрыло число 3. А число 5 закрыло число 4. Поэтому
если мы попытаемся достать оттуда значение, достанется именно число
5. Следующим достанется число 4, а потом 3.
В "идеале" число чисел (букв, значков, символов), которые можно положить
в стек - бесконечно. Но на практике конечно это далеко не так. Объемы
памяти ограничены, поэтому, чтобы стек не переполнился - его нужно
заводить нужной длины.
Как вы понимаете, стек поддерживает две операции - положить элемент
(операция называется PUSH) и вытащить элемент (операция называется POP).
Кроме того, нам очевидно понадобится указатель стека (это некоторое
число, указывающее на текущий последний элемент стека). В нашем
примере указатель будет указывать на число 5.
Чтобы реализовать операцию PUSH нужно сделать две вещи - сдвинуть
указатель на единицу (чтобы он указывал не на последнее число, а на
первое пустое место). Ну и положить на это пустое место новое число.
Реализовать операцию POP тоже просто - нужно лишь вернуть число, которое
находится в памяти, на которую указывает указатель - и уменьшить
указатель на единицу - к предыдущему числу.
Вообще по науке надо бы еще и проверять - не положили ли мы чисел больше
чем помещается в стек или пытаемся извлечь число, когда стек пуст - но
можно просто сделать так, чтобы этого не происходило.
А зачем вообще нужен стек? Ну например для вычисления выражений. Например, как вычисляет выражение 1+2*4+3 человек? Умножает 2 на 4, добавляет 1, а потом добавляет 3. А компьютер?
Заносит в стек левое множимое - 2
Заносит в стек правое множимое - 4
Достает из стека два числа (4,2) и перемножает - 8. Кладет это число в стек
Заносит в стек слагаемое - 1
Достает из стека два числа (1,8) и складывает - 9. Кладет это число в стек
Заносит в стек слагаемое - 3
Достает из стека два числа (3,9) и складывает - 12.
Вот вам одно из применений стека - вычисление математических выражений. Математический сопроцессор в любом современном компьютере именно так и работает (правда там стек не бесконечный - туда только 8 чисел помещается).