АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Представление стека в виде вектора

Чаще всего стек представляется в виде вектора с указателем (рис. 3.6).

Рис. 3.6. Хранение стека в виде вектора

Часть вектора занимает стек, часть - свободное пространство. Указателем стека служит индекс последнего из поступивших элементов (либо индекс первой свободной позиции). Указатель стека увеличивается на единицу при вталкивании элемента и уменьшается при выталкивании (или наоборот, если стек расположен в конце вектора).

Два стека удобно хранить в одном векторе, заполняя их навстречу друг другу (рис. 3.7).

Рис. 3.7. Хранение двух стеков в одном векторе

Этот способ позволяет расти любому из двух стеков, пока есть хотя бы одна свободная ячейка. Максимальные размеры каждого стека и их суммы равны длине вектора. Для большего количества стеков подобного метода не существует.

Пример 3.9. Описание данных для представления стека вектором

#define N 100 /* Максимальная длина стека */

Тип-элемента st[N]; /* Отображающий вектор стека */

int ist; /* Указатель стека (индекс последнего элемента) */

Пример 3.10. Инициализация (создание) пустого стека:

ist = -1;

Как и в очереди, при невозможности выполнения операции действия зависят от решаемой задачи. Обычно пустота стека используется как условие окончания алгоритма, а переполнение означает ошибку.

Пример 3.11. Выталкивание из стека элемента и присваивание его величине x (обозначим эту операцию Стек ==> x; без запоминания элемента: Стек ==>):

Тип-элемента x; /* Значение вытолкнутого элемента */

...

if (ist >= 0) /* В стеке есть элементы */

{ x = st[ist]; /* Получение значения */

ist--; /* Выталкивание элемента */

}

else ... /* Стек пуст */

Пример 3.12. Вталкивание в стек элемента, равного x (обозначим эту операцию Стек <== x):

Тип-элемента x; /* Вталкиваемое значение */

...

if (ist < N-1) /* Есть место в стеке */

{ ist++; /* Увеличение стека */

st[ist] = x; /* Запись x в вершину стека */

}

else ... /* Стек переполнен */

Дата добавления: 2015-09-27 | Просмотры: 479 | Нарушение авторских прав