Стеком называется упорядоченный набор элементов, в котором размещение новых и удаление существующих происходит с одного конца, называемого вершиной.
Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных.
В зависимости от дисциплины обслуживания различают те или иные структуры динамических данных.
Принцип работы стека сравнивают со стопкой листов бумаги: чтобы взять второй сверху, нужно снять верхний.
В стеке реализуется дисциплина обслуживания 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;
}
Результат выполнения
Назад: Структуры данных
2
3
4
5
6
typedef struct atom {
TYP h; //
struct atom *nasl; //rekurzivna cas struktury
}ATOM;
Прокомментируйте пожалуйста по подробнее строчку :
Мне сразу сходу трудно в этом разобраться :-)
Такую строчку ещё могу с грехом пополам переварить :
Видимо, приложить усилия и разобраться сложнее, чем размещать подобные комментарии. Удачи в изучении.