Раздел «Язык Си».CoffeStack:

Стек

Стек (stack) - абстрактный тип данных, представляющий последовательность элементов, организованных по принципу LIFO ("last in first out" - последним пришел, первым вышел).

Рисунок1 (пирамидка, башенка)

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

Реализация стека основывается на двух методах (функциях):

Для удобства работы можно объявить еще функции, например, print (распечатать содержимое стека, бесценно для отладки), is_empty (это пустой стек?), top (вернуть элемент сверху стека, содержимое стека НЕ изменяется) и так далее.

Рисунок2 (кладем цвета в стек, достаем их из стека).

Для решения каких задач может использоваться стек?

Примеры использования стека

Вычисление постфиксной записи

Мы привыкли записывать арифметические выражения в инфиксной форме, где оператор (сложить, умножить) стоит между операндами.

2 + 3 =

Это же выражение можно записать в постфиксной форме, где оператор стоит после операндов.

2 3 + =

Infix Postfix
2 + 3 2 3 +
2 + 3 - 4 2 3 + 4 -
2 * 3 + 4 * 5 2 3 * 4 5 * +
2 + 3 * 4 + 5 2 3 4 * + 5 +
(2 + 3) * (4 + 5) 2 3 + 4 5 + *

Заметим, что для указания приоритета операций в инфиксной записи нужны скобки, а в постфиксной скобок не нужно.

Как вычислить значение постфиксного выражения с помощью стека?

Будем класть в стек числа по следующим правилам:

Разберем, как работает этот алгоритм и что лежит в стеке на примере вычисления выражения "(1 + 2) * (3 + 4)". В постфиксной форме это "1 2 + 3 4 + *"

Рисунок3. Вычисление постфиксной записи "1 2 + 3 4 + *"

Перевод из инфиксной записи в постфиксную

TODO

Вычисление инфиксной записи с помощью стека

TODO

Реализация стека на основе массива фиксированной длины

Пусть в стеке хранятся данные типа Data (мы будем пока считать и использовать в дальнейших примерах, что это тип int).

typedef int Data;

В качестве стека объявим массив из 10 элементов типа Data. Сразу положим в стек значения 5, 7, -3

#define N 10

Data a[N];

Положим в этот стек числа 5, 7, -3:

a[0] = 5;
a[1] = 7;
a[2] = -3;

Рисунок: стек с числами, вопросительными знаками и индексами.

Решим простейшую задачу - распечатаем содержимое стека.

Но как мы узнаем, где заканчиваются данные и начинается "мусор"? Мы не можем сделать специальное значение, как в строках '\0', чтобы пометить конец данных. Если решим использовать 0 как "конец данных", то как нам хранить значение 0?

Давайте, как в случае длинной арифметики, будем хранить информацию о том, где заканчиваются данные в переменной n.

Можно хранить в n, как в длинной арифметики, индекс последней ячейки с данными. n = 2;

Можно хранить в n индекс первой пустой ячейки или количество ячеек с данными. n = 3;

Что выбрать?

Рассмотрим пустой стек. В индекс "последней ячейки с данными" будет -1, а количество хранимых чисел (или индекс первой пустой ячейки) 0. Выберем второй вариант (он понятнее для пустого стека).

Так как массив а - это ячейки стека, а n - счетчик стека, то стоит эти переменные хранить вместе, в одной структуре. Назовем ее Stack.

struct Stack{
    Data a[N];   // элементы стека
    int n;       // сколько элементов хранится в стеке
};

Теперь в функции main создадим стек (сразу с данными, как на рисунке выше) и попробуем распечатать его содержимое:

(Мы будем "есть медведя по кускам" - сначала писать наброски кода, потом оформлять их в отдельную функцию. Если вы сразу можете придумать, как написать функцию печати стека, напишите ее и отладьте. Потом читайте дальше.)

Рисунок: массив а и поле n объединены в структуру, переменная называется st

int main() {
    struct Stack st = {{5, 7, -3}, 3};  // Data a[N] = {5, 7, -3}, int n = 3;
    // печатаем содержимое стека
    int i;
    for(i = 0; i < st.n; i++) {
        print("%d ", st.a[i]);
    printf("\n");
    return 0;
}

Выделим код печати в отдельную функцию stack_print. Она ничего не должна возвращать. Передавать в нее будем стек.

Вопрос - что лучше передать в функцию - копию структуры или ее адрес?

Копировать массив (внутри структуры) - нехорошо. Лучше передадим на него указатель.

void stack_print(struct Stack * s) {
    int i;
    for(i = 0; i < s->n; i++) {
        print("%d ", s->a[i]);
    printf("\n");
}
int main() {
    struct Stack st = {{5, 7, -2}, 3};
    stack_print(&st);  // 5 7 -2
    return 0;          
}

Добавим на вершину стека число 11. Стек растет в сторону больших индексов массива.

Поле n - номер первой пустой ячейки, куда будем добавлять новое значение.

Написать функцию нужно так, чтобы после ее использования печать по-прежнему работала правильно. Функция stack_push должна аналогично stack_print ничего не возвращать, в нее должен передаваться стек (передадим его адрес) и туда должно передаваться значение data, которое мы кладем в стек.

Напишем сначала проверку работы этой функции в main:

int main() {
    struct Stack st = {{5, 7, -2}, 3};
    stack_print(&st);      // 5 7 -2
    stack_push(&st, 11);
    stack_print(&st);      // 5 7 -2 11
    return 0;          
}

После этого реализуем функцию stack_push

void stack_push(struct Stack * s, Data data) {
    s->a[s->n] = data;
    s->n ++;    
}

Аналогично допишем тесты на stack_pop и реализуем эту функцию.

void stack_print(struct Stack * s) {
    int i;
    for(i = 0; i < s->n; i++) {
        print("%d ", s->a[i]);
    printf("\n");
}
int main() {
    Data d;
    struct Stack st = {{5, 7, -2}, 3};
    stack_print(&st);      // 5 7 -2

    stack_push(&st, 11);
    stack_print(&st);      // 5 7 -2 11

    d = stack_pop(&st);
    stack_print(&st);      // 5 7 -2
    printf("d = %d\n", d); // d = 11
    
    return 0;          
}

Заметьте, ни в stack_push, ни в stack_pop нет проверок - не вышли ли мы за границы массива. Пусть эти проверки делает пользователь нашей библиотеки функций работы со стеком. Для этого дадим ему функции stack_is_empty и stack_is_full. В функции передают указатель на стек и они возвращают истину или ложь (с точки зрения языка С).

Реализуйте эти функции самостоятельно.

Вопрос: можно ли создать работоспособный стек так:

struct Stack st;
stack_print(&st);

Быть может, вторая строка приведет к падению программы.

Потому что если st - локальная переменная, то в поле n может быть любое число. Например, -147. Цикл в функции stack_print при этом выйдет далеко за границы выделенной памяти.

Значит, нужна функция, которая бы готовила стек к работе. Назовем ее stack_init.

void stack_init(struct Stack * s) {
    s->n = 0;
}
int main() {
    struct Stack st;

    stack_init(&st);       // без init другие функции работы со стеком будут работать неправильно

    stack_push(&st, 5);
    stack_push(&st, 7);
    stack_push(&st, -2);
    stack_print(&st);      // 5 7 -2

    return 0;
}

Контрольный вопрос: В каких функциях передача стека по значению привела бы к полной неработоспособности функции:

Стек на основе динамического массива

Стек, написанный выше, плох тем, что в него нельзя положить больше N элементов. И это N задано на этапе компиляции.

В конкретной задаче можно предположить, какой размер стека взять, но если мы пишем библиотеку функций, которыми будут пользоваться разные программисты, мы ничего не можем сказать об их задачах.

Сделаем N большое, но во-первых, это сегодня N достаточно большое, а через год у нас может появиться задача с еще большим набором данных.

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

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

Что для этого надо изменить?

То есть у нас две разных характеристики - сколько данных хранится в стеке (число n) и на сколько данных выделена память (число size). n <= size

Структура данных Stack:

struct Stack {
    Data * a;            // указатель на динамически выделенную память под элементы стека
    unsigned int size;   // на сколько элементов выделена память
    unsigned int n;      // сколько элементов хранится в стеке
};

Какие функции не изменятся?

Пусть функция stack_init создает пустой стек на 10 элементов.

#define N 10
void stack_init(struct Stack * s) {
    s->n = 0;       // пустой стек
    s->size = N;    // емкостью N элементов
    s->a = malloc(s->size * sizeof(Data));
}

В функцию stack_push нужно дописать это "саморасширение". Пусть каждый раз стек увеличивается на N элементов.

Есть разные стратегии увеличения размера стека - на постоянную величину, на сколько-то процентов и так далее. Выберите сами.

void stack_push(struct Stack * s, Data data) {
    // если стек полон, его нужно увеличить на 10 элементов
    if (s->n == s->size) {
        s->size += N;
        s->a = realloc(s->a, s->size * sizeof(Data));
    }
    s->a[s->n] = data;
    s->n ++;    
}

Напишите функцию main для тестирования работы этого стека. Запустите полученный код под valgrind. Утечка памяти? Значит в наборе функций не хватает функции создания и удаления стека stack_new и stack_delete.

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

Функция stack_delete должна получать стек, освобождать память (и возвращать NULL????);

struct Stack * s = stack_new();

stack_push(s, 5);
stack_push(s, 7);
stack_push(s, -2);
stack_print(s);

stack_delete(s);   // или s = stacke_delete(s); ????

Рисунок: Порядок выделения памяти в stack_new

Как видно из рисунка, выделить память и инициализировать поля нужно в следующем порядке:

  1. выделить память под сам стек (поля a, n, size).
  2. инициализировать поле n
  3. инициализировать поле size
  4. выделить память под динамический массив элементов стека и сохранить его адрес в поле а.

struct Stack stack_new() {
   struct Stack * s;
   s = malloc(sizeof(struct Stack));    // пункт 1
   stack_init(s);                       // пункты 2, 3, 4
   return s;
}

Функцию stack_delete напишите самостоятельно.

Обратите внимание, что если при создании стека функция malloc была использована 2 раза, то и функция free должна быть вызвана тоже 2 раза.

Подумайте в каком порядке надо ее вызвать для указателя на стек s и указателя на массив элементов s->a.

Стек с выделением всей необходимой памяти единым куском

Ответы на контрольные вопросы

Стек на основе фиксированной длины

Только те функции, которые не изменяют содержимого полей стека. Это stack_print, stack_size, stack_is_empty, stack_is_full.

-- TatyanaDerbysheva - 08 Jan 2019