Стек в информатике

Введение

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

Принцип действия стека можно сравнить с пачкой бумажных листов, которые лежат в коробке на столе. Для того, чтобы взять, к примеру, третий считая от верхнего лист, необходимо сначала достать два листа, лежащих сверху. То есть в стеке используется дисциплина обслуживания LIFO, что означает:

1. Last переводится как последний.
2. Input означает вход.
3. First в переводе означает первый.
4. Output означает выход.

То есть дословно это: последним вошёл, первым вышел.

В области цифровых электронных вычислительных комплексов стек часто именуется магазином. То есть, имеется ввиду, аналогия с размещением патронов в магазине огнестрельного оружия. При этом первый выстрел будет сделан патроном, который заряжался последним.

Понятие стека было введено в обиход в середине сороковых годов двадцатого века Аланом Тьюрингом, но патент на саму реализацию стека получили в конце пятидесятых годов прошлого века немецкие специалисты Клаус Самельсон и Фридрих Бауэр. В отдельных языках программирования стеком могут считаться любые списки, поскольку они способны использовать функции pop и push.

Виды стековой организации

В информатике и программировании организация стека делится на следующие виды:

1. Аппаратная организация стека. Применяется для сохранения адреса возврата из подпрограммы (функции) и их параметров (аргументов).
2. Программная стековая организация. Эта организация стека, которая предназначается для программ (подпрограмм) пользователя.

Срочно нужна работа?
Мы готовы помочь!

Найти эксперта

Для взаимодействия со стековой организацией информационных данных, предназначены следующие операции:

1. Для инициализации стека используется ìnit(s). Здесь s обозначает стек.
2. Чтобы поместить в стек новые данные, служит функция push(s, i). Здесь s также означает стек, а ì это сам компонент данных.
3. Чтобы удалить компонент из стека, служит команда ì=pop(s).
4. Чтобы определить верхний компонент и не удалять его, используется функция i=stkTop(s).
5. Чтобы получить вершину стека (число компонентов), служит команда i=gettop(s).
6. Для распечатки содержимого стека используется функция stkPrint(s).
7. Чтобы определить пустой стек или в нём есть элементы, применяется функция isempty(s). Она делает возврат значения true при пустом стеке и false, если он не пустой.

Практическая организация стека

Стек возможно организовать следующими способами:

1. При помощи одномерного массива.
2. При помощи связанного списка.
3. При посредстве класса объектно-ориентированного программирования.

Приведём пример практической реализации стековой структуры:

#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 — интернет-биржа студенческих работ

Срочно нужна работа?
Мы готовы помочь!

Найти эксперта