Реализация стека (пример использования структур)

Практический курс по C/C++: https://stepik.org/course/193691

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

Я напомню, что стек – это такая структура данных, которая добавляет новые объекты наверх и извлекает тоже сверху. Получается очередь, в которой последний добавленный объект извлекается первым. Сокращенно по-английски эта аббревиатура звучит как:

LIFO (Last In, First Out)

Структура стека в нашей реализации будет выглядеть следующим образом:

Здесь top – это указатель на самый верхний объект; next – указатель на следующий объект стека. Самый нижний элемент имеет значение указателя next равное NULL. Это будет маркер конца стека.

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

typedef struct tag_obj {
    int data;
    struct tag_obj* next;
} OBJ;

Она содержит целочисленное поле data – это данные, которые мы сохраняем в объектах стека, и указатель next. Обратите внимание, как задан тип указателя. Мы используем тип текущей структуры внутри нее самой. Компилятор языка Си позволяет нам это делать, но только для определения указателей. Обычные переменные внутри структуры ее же типа объявлять нельзя. Это, так называемый, неполный тип. Прописывать вместо него, например, тип OBJ не получится, так как на этот момент он еще просто неизвестен.

Далее, в функции main() мы объявим указатель top с начальным значением NULL:

int main(void) 
{
    OBJ* top = NULL;
 
    return 0;
}

Это будет означать, что стек пуст, то есть, не содержит ни одного элемента. Для добавления нового объекта в стек определим функцию с именем push():

OBJ* push(OBJ* top, int data)
{
    OBJ* ptr = malloc(sizeof(OBJ));
    ptr->data = data;
    ptr->next = top;
    return ptr;
}

В качестве параметров она принимает указатель на вершину стека и данные, которые нужно сохранить в добавляемом элементе. В теле функции сначала создается новый объект для структуры; в поле data сохраняется переданное значение; указателю next присваивается значение адреса указателя top (так как мы добавляем объект на верх стека); возвращаем адрес нового созданного объекта (вершины стека).

Воспользоваться этой функцией можно следующим образом:

int main(void) 
{
    OBJ* top = NULL;
 
    top = push(top, 1);
    top = push(top, 2);
    top = push(top, 3);
    top = push(top, 4);
 
    return 0;
}

Мы здесь последовательно добавляем четыре объекта и каждый раз меняем значение указателя top, чтобы он ссылался на самый верхний объект, тот, что был добавлен в последнюю очередь.

Следующая функция будет извлекать самый верхний объект из стека, удаляя его:

OBJ* pop(OBJ* top)
{
    if(top == NULL)
        return top;
    
    printf("Deleted: %d\n", top->data);
 
    OBJ* ptr_next = top->next;
    free(top);
 
    return ptr_next;
}

Мы также передаем указатель на вершину стека и далее проверяем, если указатель равен NULL, значит, стек пуст и удалять нечего, завершаем функцию. Если же объекты есть, то создаем временный указатель ptr_next на следующий объект стека и освобождаем память из под текущего верхнего объекта. В конце возвращаем адрес следующего (но теперь верхнего) элемента стека.

Наконец, последняя функция, будет перебирать все элементы стека и отображать их на экране:

void show_stack(const OBJ* top)
{
    const OBJ* current = top;
    while(current != NULL) {
        printf("%d\n", current->data);
        current = current->next;
    }
}

Для этого реализован цикл while, пока мы не дойдем до последнего элемента, адрес которого равен NULL. В цикле выполняется отображение поля data текущего объекта и переход к следующему, используя указатель next.

Всеми этими функция можно воспользоваться так:

int main(void) 
{
    OBJ* top = NULL;
 
    top = push(top, 1);
    top = push(top, 2);
    top = push(top, 3);
    top = push(top, 4);
 
    show_stack(top);
 
    while(top)
        top = pop(top);
 
    return 0;
}

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

4
3
2
1
Deleted: 4
Deleted: 3
Deleted: 2
Deleted: 1

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

Практический курс по C/C++: https://stepik.org/course/193691

Реализация стека (пример использования структур)

Видео по теме