Стек


 

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

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

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

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

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

Результат выполнения
Результат перевода числа в другую систему счисления


Назад: Структуры данных

Комментариев к записи: 16

  • Здравствуйте. Я сейчас пытаюсь разобраться со стэком реализованный при помощи рекурсивной структуры. Но не совсем понимаю в чем разница и как она работает. Не могли бы вы помочь разобраться, ниже пример структуры для стэка
    1
    2
    3
    4
    5
    6
    typedef int TYP; 

    typedef struct  atom {
        TYP h; //
        struct atom *nasl; //rekurzivna cas struktury
    }ATOM;


  • Константин
    Елена, привет!
    Прокомментируйте пожалуйста по подробнее строчку :
    1
    stk = (struct stack*)malloc(sizeof(struct stack));

    Мне сразу сходу трудно в этом разобраться :-)
    Такую строчку ещё могу с грехом пополам переварить :
    1
    int* ptr = (int*)malloc(sizeof(int));

    • Елена Вставская
      Точно такое же выделение памяти, только в качестве типа данных используется пользовательская структура данных. int заменено на struct stack.

  • Студент
    Просто поганое оформление! Ни номеров строк, ни комментариев, что зачем идет, ничего! Просто скопировали текст и парьтесь как хотите! Поймете, дак поймете - нет, значит нет, и плевать на вас! Коды выделите в отдельные рамки, строки пронумеруйте, добавьте комментарии, версию компилятора и имя платформы (далеко не все программы с x64 работают на x86 и наоборот). Метод malloc на MVS 2019 уже не безопасен и компилятор выдает ошибку. Зачем вы его здесь приводите? Одно слово: делала женщина!

    • Елена Вставская
      Ну, покажите свой сайт. Высокого качества, который Вы, как мужчина, сделали.

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

    • Елена Вставская
      Пожалуйста)
      Видимо, приложить усилия и разобраться сложнее, чем размещать подобные комментарии. Удачи в изучении.

      • Нет, просто ваш веб-сайт очень низкого качества! Богдан в этом отношении прав.

  • Подскажите пожалуйста, а зачем инициализируется структура без её полей? Точнее указатель на неё, это для чего?

    • Елена Вставская
      Видимо, чтобы потом ее заполнить. Не совсем поняла вопрос. Можно "цитату из кода"?

      • Какую цитату? Вас даже строки не пронумерованы! Доведите оформление до ума, а не просто сплошной текст на отвяжись.


    • Елена Вставская
      Реализована. В имени этой функции была опечатка. Спасибо.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *