Стек

Стек

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

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

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

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

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

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

21 комментарий к “Стек”

  1. Виктор Рыжков

    Спасибо за Ваш сайт, он один из лучших для изучения C и алгоритмов. Не обращайте внимание на глупые комментарии, все отлично разобрано, с примерами. Столько потрачено труда — Вы замечательная)

  2. Дмитрий

    Спасибо за сайт и материал. Те, кто жалуются — просто не имеют желания разбираться.

  3. Здравствуйте. Я сейчас пытаюсь разобраться со стэком реализованный при помощи рекурсивной структуры. Но не совсем понимаю в чем разница и как она работает. Не могли бы вы помочь разобраться, ниже пример структуры для стэка

    1
    2
    3
    4
    5
    6
    typedef int TYP; 

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

  4. Константин

    Елена, привет!

    Прокомментируйте пожалуйста по подробнее строчку :

    1
    stk = (struct stack*)malloc(sizeof(struct stack));

    Мне сразу сходу трудно в этом разобраться 🙂

    Такую строчку ещё могу с грехом пополам переварить :

    1
    int* ptr = (int*)malloc(sizeof(int));
    1. Елена Вставская

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

  5. Студент

    Просто поганое оформление!

    Ни номеров строк, ни комментариев, что зачем идет, ничего! Просто скопировали текст и парьтесь как хотите! Поймете, дак поймете — нет, значит нет, и плевать на вас!

    Коды выделите в отдельные рамки, строки пронумеруйте, добавьте комментарии, версию компилятора и имя платформы (далеко не все программы с x64 работают на x86 и наоборот).

    Метод malloc на MVS 2019 уже не безопасен и компилятор выдает ошибку. Зачем вы его здесь приводите?

    Одно слово: делала женщина!

    1. Елена Вставская

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

  6. Богдан

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

    1. Елена Вставская

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

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

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

    1. Елена Вставская

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

      1. Елена

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

Оставьте комментарий

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

Прокрутить вверх