Стек

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

Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных.

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

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

В стеке реализуется дисциплина обслуживания 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 — стек

Способы реализации стека

Существует несколько способов реализации стека:

с помощью одномерного массива;
с помощью связанного списка;
с помощью класса объектно-ориентированного программирования.

Пример реализации стека с помощью одномерного массива

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

1
2
3
4
5

#define NMAX 100
struct stack {
float elem[NMAX];
int top;
};

NMAX — максимальное количество элементов в стеке;
elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека;
top — индекс элемента, находящегося в вершине стека.

Инициализация стека

Индекс элемента, находящегося в вершине стека, равен 0.

1
2
3

void init(struct stack *stk) {
stk->top = 0;
}

Помещение элемента в стек

В элемент массива с индексом top записывается значение f. После этого вершина стека, соответствующая количеству элементов в массиве, перемещается на 1 элемент влево.

1
2
3
4
5
6
7

void push(struct stack *stk, float f) {
  if(stk->top < NMAX) {
    stk->elem[stk->top] = f;
    stk->top++;
  } else
    printf("Стек полон, количество элементов: %d !\n", stk->top);
}

Удаление элемента из стека

Если в массиве, соответствующем стеку, есть элементы, то количество элементов уменьшается на 1. После этого возвращается последний элемент.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

float pop(struct stack *stk) {
  float elem;
  if((stk->top) > 0)
  {
    stk->top--;
    elem = stk->elem[stk->top];
    return elem;
  }
  else
  {
    printf("Стек пуст!\n");
    return 0;
  }
}

Получение верхнего элемента стека без его удаления

1
2
3
4
5
6
7
8

float stkTop(struct stack *stk) {
  if((stk->top) > 0) {
    return stk->elem[stk->top-1];
  } else {
    printf("Стек пуст!\n");
    return 0;
  }
}

Получение количества элементов стека

1
2
3

int getcount(struct stack *stk) {
return stk->top;
}

Определение, пуст ли стек

Если количество элементов в стеке равно 0, то стек пуст (возвращается 1).

1
2
3
4

int isempty(struct stack *stk) {
if(stk->top == 0) return 1;
else return 0;
}

Вывод элементов стека

Если стек не пуст, движемся от последнего элемента к началу массива с выводом элементов.

1
2
3
4
5
6
7
8
9

void stkPrint(struct stack *stk) {
  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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int main() {
  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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int main() {
  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;
}

Результат выполнения