Структуры данных типа стек. Реализация стека как отображения на массив и односвязный список. Примеры применения.

Стек – это последовательность, в которой включение и исключение элемента осуществляется с одной стороны последовательности (вершины стека). Так же осуществляется и операция доступа. Структура функционирует по принципу LIFO (последний пришедший обслуживается первым). Условные обозначения стека:

При реализации стека рассматриваются стек как отображение на массив и стек как отображение на список.

Совокупность операций, определяющих структуру типа стек:

1. Операция инициализации.

2. Операция включения элемента в стек.

3. Операция исключения элемента из стека.

4. Операция проверки: стек пуст / стек не пуст.

5. Операция проверки: стек переполнен / стек не переполнен (данная операция характерна для стека как отображения на массив).

6. Операция чтения элемента (доступ к элементу).

Все операции не зависят от размерности стека, т.е. порядок временной сложности – О(1).

Имеется две модификации стека:

· Указатель находится на вершине стека, показывая на первый пустой элемент.

· Указатель указывает на первый заполненный элемент.

Стек в последовательной памяти (схема на физическом уровне):

Условные обозначения	Название стека
Нижний адрес стека
Верхний адрес стека
Адрес указателя
Описание элемента