ВУЗ:
Составители:
49
т.е. объем данных в стеке может динамически изменяться во время выполнения
программы.
Особенность стековой структуры в том, что доступ к ее элементам воз-
можен только с одного конца − вершины стека. Информация в такой структуре
обрабатывается по принципу “последним пришел – первым ушел”. Структуру
стека называют также LIFO (от англ. Last In, First Out
). Наглядной иллюстраци-
ей принципа работы стека является магазин автоматического оружия. Заполне-
ние магазина патронами возможно только с одного конца. При стрельбе первым
из магазина выходит патрон, попавший туда последним. вторым – предпослед-
ним и т.д., последним из магазина выйдет патрон, попавший в него первым.
Структура стека является структурой данных с
ограниченным досту-
пом, так как доступ возможен только к элементу, находящемуся в вершине сте-
ка. Элемент в вершине стека называется текущим. Информацию о позиции
текущего элемента стека хранит указатель вершины стека (УВС), размещае-
мый обычно в головной ячейке стека.
Для хранения стеков может использоваться как последовательное, так и
связанное представление
данных.
При последовательном представлении необходимо знать предельный
размер стека. Под этот размер резервируется блок памяти, внутри которого стек
растет и сокращается. Первая ячейка блока содержит указатель вершины стека.
Когда стек пуст, указатель указывает на самого себя. При включении каждого
последующего элемента указатель вершины увеличивается на единицу (рис.
4.3.).
Доступ к стеку
может быть организован так, чтобы значение указателя
вершины оставалось неизменным в течение всего времени существования стека.
В этом случае доступ осуществляется всегда к одной и той же ячейке блока па-
мяти, зарезервированного под стек. На эту ячейку устанавливается указатель
вершины и в ней хранится текущий (верхний) элемент стека. При включении
или
исключении элемента все остальные элементы стека перемещаются вниз
или вверх соответственно внутри блока памяти (рис 4.4).
В этом случае операции включения и исключения называются соответ-
ственно “проталкиванием” и “выталкиванием”. Недостаток такого представле-
ния стека состоит в том, что всегда остается опасность переполнения стека. По-
пытки избежать этого за счет резервирования большей
памяти под стек приво-
дят к неэкономному ее использованию.
a
n-1
…
a
2
a
1
УВС
Свободная
память
a
n
a
n-1
…
a
2
a
1
УВС
Свободная
память
a
n
a
n-1
…
a
2
a
1
УВС
Свободная
память
a
n+1
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
