Стеки

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

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

Когда мы пишем какой-то адрес в адресной строке нашего бразузера (например, google.ru), то он помещается (или как говорят вталкивается) в стек:

Текущий адрес является вершиной стека. Например, мы хотим найти определение стека, тогда мы пишем слово Стек в поисковой строке и нажимаем Поиск, в наш стек помещается еще один элемент, это новый адрес (например, https://www.google.ru/webhp?hl=ru#newwindow=1&hl=ru&q=стек), а поисковая система отвечает нам списком ранжированных страниц. Предположим, что в какой-то момент времени наш стек выглядит следующим образом:

Тогда нажимая на кнопку назад из стека будет выталкиваться один элемент и осуществляться переход на страницу, которая находится в новой вершине стека. Вопрос: Как же тогда может быть осуществлен переход по кнопке вперед? Логично предположить, что когда элемент со стека снимается, то он помещается в другой стек, таким образом, существует два стека, один для кнопки вперед, другой для кнопки назад:

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

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

typedef int stack_element_t;

typedef struct
{
    stack_element_t *elements;
    size_t max_size;
    int top;
} stack_t;

Где elements это массив значений, хранящихся в стеке, max_size - максимальный размер стека, top - указатель на вершину стека.

Операции над стеком

Список операций, которые мы будем выполнять над стеками:

• stack_init(S, max_size) - создание стека S размера max_size;
• stack_push(S, x) - добавление элемента x в стек S;
• stack_pop(S) - удаление элемента с вершины стека S;
• stack_top(S) - получение значения элемента, находящегося в вершине стека S;
• stack_is_full(S) - проверка стека S на полноту;
• stack_is_empty(S) - проверка стека S на пустоту;
• stack_is_print(S) - печать содержимого стека S;
• stack_is_destroy(S) - уничтожение стека S.

Реализация

При создании стека выделяется память под max_size элементов типа stack_element_t:

void stack_init(stack_t *S, size_t max_size)
{
    stack_element_t* new_elements;

    new_elements = (stack_element_t *)malloc(sizeof(stack_element_t) * max_size);
    if (new_elements == NULL)
    {
        fprintf(stderr, "Error: Can't allocate memory\n");
        exit(1);
    }

    S->elements = new_elements;
    S->max_size = max_size;
    S->top = -1;
}

Уничтожение стека и освобождение памяти равнее выделенной под массив elements:

void stack_destroy(stack_t *S)
{
    free(S->elements);
    S->elements = NULL;
    S->max_size = 0;
    S->top = -1;
}

Проверка стека на полноту и пустоту:

bool stack_is_full(stack_t *S)
{
    return S->top >= S->max_size - 1;
}

bool stack_is_empty(stack_t *S)
{
    return S->top < 0;
}

Добавление и удаление элемента с вершины стека:

void stack_push(stack_t *S, stack_element_t x)
{
    if (stack_is_full(S))
    {
        fprintf(stderr, "Error: Stack overflow\n");
        exit(1);
    }
    S->elements[++S->top] = x;
}

stack_element_t stack_pop(stack_t *S)
{
    if (stack_is_empty(S))
    {
        fprintf(stderr, "Error: Stack is empty\n");
        exit(1);
    }
    return S->elements[S->top--];
}

Получение значения находящегося в вершине стека:

stack_element_t stack_top(stack_t *S)
{
    if (stack_is_empty(S))
    {
        fprintf(stderr, "Error: Stack is empty\n");
        exit(1);
    }
    return S->elements[S->top];
}

Печать содержимого стека, предполагая, что в стеке хранятся символы:

void stack_print(stack_t *S)
{
    for (int i = S->top; i >= 0; i++)
       printf("[%i] %c\n", i, S->elements[i]);    
}

В качечтве примера использования стека напишем функцию reverse(str), которая переворачивает строку str:

void reverse(char *str)
{
    stack_t S;
    stack_init(&S, strlen(str));
    // помещаем все элементы строки в стек, кроме нулевого символа
    for (int i = 0; str[i] != '\0'; i++)
        stack_push(str[i]);

    // из стека выталкиваем все элементы обратно в строку, но уже
    // в обратном порядке
    int i = 0;
    while (!stack_is_empty(S))
        str[i++] = stack_pop(S);
    str[i] = '\0';
    stack_destroy(S);
}

Задания

Задание 1: Напишите функцию isBalanced(str), которая проверяет соответствует ли каждой отрывающей скобке ((, {, [, <) закрывающая (), }, ], >) в строке str, если это так, то функция должна вернуть true, в противном случае false.

Задание 2: Напишите функицю eval_expr(str), которая вычисляет выражение в строке str, записнное в обратной польской нотации, например, eval_expr("1 2 + 4 × 3 +") должно быть равно 15.

Задание 3: Напишите функцию multipop(S, k), которая выталкивает из стека k элементов и возвращает значение последнего вытолкнутого. В случае если k больше чем размер стека S, то следует просто вытолкнуть все элементы.