Стек в информатике — это абстрагированная структура данных, которая представляет собой набор компонентов, сформированных по правилу вошёл последним, вышел первым.
Введение
Под стеком понимается организованный список компонентов, в котором занесение новых и вывод имеющихся в наличии, выполняется только с его вершины
Дисциплиной обслуживания считается набор правил, которые предназначены для работы с компонентами структурированных данных в динамическом режиме. Дисциплины обслуживания определяют виды структур динамической организации данных.
Принцип действия стека можно сравнить с пачкой бумажных листов, которые лежат в коробке на столе. Для того, чтобы взять, к примеру, третий считая от верхнего лист, необходимо сначала достать два листа, лежащих сверху. То есть в стеке используется дисциплина обслуживания LIFO, что означает:
- Last переводится как последний.
- Input означает вход.
- First в переводе означает первый.
- Output означает выход.
То есть дословно это: последним вошёл, первым вышел.
В области цифровых электронных вычислительных комплексов стек часто именуется магазином. То есть, имеется ввиду, аналогия с размещением патронов в магазине огнестрельного оружия. При этом первый выстрел будет сделан патроном, который заряжался последним.
Понятие стека было введено в обиход в середине сороковых годов двадцатого века Аланом Тьюрингом, но патент на саму реализацию стека получили в конце пятидесятых годов прошлого века немецкие специалисты Клаус Самельсон и Фридрих Бауэр. В отдельных языках программирования стеком могут считаться любые списки, поскольку они способны использовать функции pop и push.
Виды стековой организации
В информатике и программировании организация стека делится на следующие виды:
- Аппаратная организация стека. Применяется для сохранения адреса возврата из подпрограммы (функции) и их параметров (аргументов).
- Программная стековая организация. Эта организация стека, которая предназначается для программ (подпрограмм) пользователя.
Для взаимодействия со стековой организацией информационных данных, предназначены следующие операции:
- Для инициализации стека используется ìnit(s). Здесь s обозначает стек.
- Чтобы поместить в стек новые данные, служит функция push(s, i). Здесь s также означает стек, а ì это сам компонент данных.
- Чтобы удалить компонент из стека, служит команда ì=pop(s).
- Чтобы определить верхний компонент и не удалять его, используется функция i=stkTop(s).
- Чтобы получить вершину стека (число компонентов), служит команда i=gettop(s).
- Для распечатки содержимого стека используется функция stkPrint(s).
- Чтобы определить пустой стек или в нём есть элементы, применяется функция isempty(s). Она делает возврат значения true при пустом стеке и false, если он не пустой.
Практическая организация стека
Стек возможно организовать следующими способами:
- При помощи одномерного массива.
- При помощи связанного списка.
- При посредстве класса объектно-ориентированного программирования.
Приведём пример практической реализации стековой структуры:
#define NMAX 100
struct stack {
float elem[NMAX];
int top;
};
Здесь:
- NMAX является самым большим допустимым количеством компонентов стека.
- elem является массивом, который может содержать NMAX числовых значений типа float и предназначается для сохранения компонентов стека.
- top является индексом верхнего компонента стека.
Пример инициализации стека, при этом индекс верхнего компонента стека приравнен к нулю:
void init(struct stack *stk) {
stk->top=0;
}
Приведём пример отправки компонента данных в стек:
Рисунок 1. Пример отправки компонента данных в стек. Автор24 — интернет-биржа студенческих работ
Пример, где удаляется компонент из стека:
Рисунок 2. Пример удаления компонента из стека. Автор24 — интернет-биржа студенческих работ
