МЕНЮ

 

Гостевая книга

Форум

 

 

КАК ОРГАНИЗОВАТЬ СТЕК

            Перво-наперво разберемся, а что же такое стек? Стек это такая гипотетическая структура, которую можно объяснить на примере.

            Пример: Все знают, как выглядит штанга. На нее одеваются блины. Но когда штангу не поднимают - блины надо куда-то ложить. Для этого есть специальные держатели - типа штырей, торчащих вверх. На них одевают диски. Главное - что если мы положили туда диски весом 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 чисел помещается).

Назад  
 

Хостинг от uCoz