Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих происходит с одного конца, называемого вершиной.
Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных.
В зависимости от дисциплины обслуживания различают те или иные структуры динамических данных.
Принцип работы стека сравнивают со стопкой листов бумаги: чтобы взять второй сверху, нужно снять верхний.
В стеке реализуется дисциплина обслуживания LIFO:
- LAST- последний
- INPUT - вошел
- FIRST - первый
- OUTPUT - вышел
Различают аппаратный и программный стек.
Аппаратный стек используется для хранения адресов возврата из функций и их аргументов.
Программный стек – это пользовательская модель (структура) данных.
Операции для работы со стеком
Над стеком реализованы следующие операции:
- инициализация стека init(s), где s — стек
- помещение элемента в стек push(s, i), где s — стек, i — помещаемый элемент;
- удаление элемента из стека i=pop(s);
- получение верхнего элемента стека без его удаления i=stkTop(s), где s — стек
- получение количества элементов стека
- определение, пуст ли стек isempty(s) возвращает 1 если стек пустой и 0 в противном случае.
- вывод элементов стека stkPrint(s), где s — стек
Способы реализации стека
Существует несколько способов реализации стека:
- с помощью одномерного массива;
- с помощью связанного списка;
- с помощью класса объектно-ориентированного программирования.
Пример реализации стека с помощью одномерного массива
Стек можно реализовать в виде следующей структуры:
2
3
4
5
struct stack {
float elem[NMAX];
int top;
};
NMAX — максимальное количество элементов в стеке;
elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека;
top — индекс элемента, находящегося в вершине стека.
Инициализация стека
Индекс элемента, находящегося в вершине стека, равен 0.
2
3
stk->top = 0;
}
Помещение элемента в стек
В элемент массива с индексом top записывается значение f. После этого вершина стека, соответствующая количеству элементов в массиве, перемещается на 1 элемент влево.
2
3
4
5
6
7
if(stk->top < NMAX) {
stk->elem[stk->top] = f;
stk->top++;
} else
printf("Стек полон, количество элементов: %d !\n", stk->top);
}
Удаление элемента из стека
Если в массиве, соответствующем стеку, есть элементы, то количество элементов уменьшается на 1. После этого возвращается последний элемент.
2
3
4
5
6
7
8
9
10
11
12
13
14
float elem;
if((stk->top) > 0)
{
stk->top--;
elem = stk->elem[stk->top];
return elem;
}
else
{
printf("Стек пуст!\n");
return 0;
}
}
Получение верхнего элемента стека без его удаления
2
3
4
5
6
7
8
if((stk->top) > 0) {
return stk->elem[stk->top-1];
} else {
printf("Стек пуст!\n");
return 0;
}
}
Получение количества элементов стека
2
3
return stk->top;
}
Определение, пуст ли стек
Если количество элементов в стеке равно 0, то стек пуст (возвращается 1).
2
3
4
if(stk->top == 0) return 1;
else return 0;
}
Вывод элементов стека
Если стек не пуст, движемся от последнего элемента к началу массива с выводом элементов.
2
3
4
5
6
7
8
9
int i;
i=stk->top; // i - количество элементов в стеке
if(isempty(stk) == 1) return; // стек пуст
do {
i--;
printf("%f\n", stk->elem[i]);
}while(i>0);
}
Пример
Создать стек из n элементов и извлечь их из стека.
Примечание: для успешной компиляции примера необходимо добавить в код программы все функции работы со стеком, описанные выше на этой странице в порядке их рассмотрения. И не забыть подключить библиотеки stdio.h, stdlib.h.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct stack *stk;
int i,n;
float elem;
stk = (struct stack*)malloc(sizeof(struct stack));
init(stk);
printf("Введите количество элементов в стеке: ");
scanf("%d", &n);
for(i=0; i<n; i++) {
printf("Введите элемент %d:", i);
scanf("%f", &elem);
push(stk,elem);
}
printf("В стеке %d элементов\n\n", getcount(stk));
stkPrint(stk);
printf("Верхний элемент %f\n",stkTop(stk));
do {
printf("Извлекаем элемент %f, ", pop(stk));
printf("в стеке осталось %d элементов\n", getcount(stk));
} while(isempty(stk) == 0);
getchar(); getchar();
return 0;
}
Результат выполнения
Пример
Перевести введенное число в систему счисления с заданным основанием.
Деление числа на основание системы счисления производится до тех пор, пока в частном не получится 0.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct stack *stk;
int n, value;
stk = (struct stack*)malloc(sizeof(struct stack));
init(stk);
printf("Введите число: ");
scanf("%d", &value);
printf("Введите основание: ");
scanf("%d", &n);
do {
push(stk, value%n);
value = value /n;
} while(value > 0);
do {
printf("%x",pop(stk)); // вывод цифры (включая цифры A...F шестнадцатеричной системы счисления
} while(isempty(stk)==0);
getchar(); getchar();
return 0;
}
Результат выполнения
Спасибо за Ваш сайт, он один из лучших для изучения C и алгоритмов. Не обращайте внимание на глупые комментарии, все отлично разобрано, с примерами. Столько потрачено труда — Вы замечательная)
Спасибо за сайт и материал. Те, кто жалуются — просто не имеют желания разбираться.
А что писать в главной функции? Как это записать?
Текст программы
Здравствуйте. Я сейчас пытаюсь разобраться со стэком реализованный при помощи рекурсивной структуры. Но не совсем понимаю в чем разница и как она работает. Не могли бы вы помочь разобраться, ниже пример структуры для стэка
2
3
4
5
6
typedef struct atom {
TYP h; //
struct atom *nasl; //rekurzivna cas struktury
}ATOM;
https://prog-cpp.ru/data-ols/
isempty(struct stack *stk) какая библиотека используется для этого ?
Никакая, тело функции приведено в тексте статьи
Елена, привет!
Прокомментируйте пожалуйста по подробнее строчку :
Мне сразу сходу трудно в этом разобраться 🙂
Такую строчку ещё могу с грехом пополам переварить :
Точно такое же выделение памяти, только в качестве типа данных используется пользовательская структура данных. int заменено на struct stack.
Просто поганое оформление!
Ни номеров строк, ни комментариев, что зачем идет, ничего! Просто скопировали текст и парьтесь как хотите! Поймете, дак поймете — нет, значит нет, и плевать на вас!
Коды выделите в отдельные рамки, строки пронумеруйте, добавьте комментарии, версию компилятора и имя платформы (далеко не все программы с x64 работают на x86 и наоборот).
Метод malloc на MVS 2019 уже не безопасен и компилятор выдает ошибку. Зачем вы его здесь приводите?
Одно слово: делала женщина!
Ну, покажите свой сайт. Высокого качества, который Вы, как мужчина, сделали.
Отлично, ровным счетом ничего не понятно. До такой степени не понятно, что я даже не могу задать вопрос, спасибо очень помогли.
Пожалуйста)
Видимо, приложить усилия и разобраться сложнее, чем размещать подобные комментарии.
Удачи в изучении.
Нет, просто ваш веб-сайт очень низкого качества! Богдан в этом отношении прав.
Или всё таки вы настолько глупы, что не можете ничего понять
Подскажите пожалуйста, а зачем инициализируется структура без её полей? Точнее указатель на неё, это для чего?
Видимо, чтобы потом ее заполнить.
Не совсем поняла вопрос. Можно «цитату из кода»?
Какую цитату? Вас даже строки не пронумерованы! Доведите оформление до ума, а не просто сплошной текст на отвяжись.
Функция stkTop(stk) не реализована?
Реализована. В имени этой функции была опечатка. Спасибо.