Обобщенный стек

Часть раздела Object Oriented Programming путешествия по C на Coddy — урок 60 из 61.

Задание

Легко

Стек — это фундаментальная структура данных, работающая по принципу «последним пришел — первым вышел» (LIFO, Last-In-First-Out). Представьте себе стопку тарелок: вы кладете новую тарелку сверху и берете тоже сверху.

Давайте создадим универсальный стек (Generic Stack) — гибкую структуру данных, которая может хранить любые типы данных с помощью указателей void*. Ваш стек будет следовать принципу LIFO и поддерживать все основные операции.

Вы организуете свой код в трех файлах:

stack.h: Определите структуру Stack с тремя полями: массив void** для элементов, int для индекса вершины (следующий свободный слот) и int для емкости (capacity). Объявите прототипы функций для создания стека (принимает емкость), добавления элемента (push), извлечения элемента (pop), просмотра верхнего элемента (peek), проверки стека на пустоту и освобождения памяти стека.
stack.c: Реализуйте ваш универсальный стек:
- create_stack — выделяет память под Stack в куче, выделяет массив элементов заданной емкости, инициализирует top значением 0 и возвращает указатель.
- push — добавляет элемент на вершину, если есть место (когда top меньше capacity).
- pop — удаляет и возвращает верхний элемент или возвращает NULL, если стек пуст.
- peek — возвращает верхний элемент без его удаления или NULL, если стек пуст.
- is_empty — возвращает 1, если в стеке нет элементов, и 0 в противном случае.
- free_stack — сначала освобождает массив элементов, а затем саму структуру Stack.
main.c: Считайте количество операций. Затем для каждой операции считайте команду: push, за которой следует целое число, pop или peek. Создайте стек емкостью 10. Для команды push выделите память под целое число в куче и поместите указатель на него в стек. Для pop извлеките элемент, выведите его значение и освободите память, выделенную под это число. Для peek выведите значение без удаления элемента. Если pop или peek вызываются для пустого стека, выведите empty. После выполнения всех операций освободите все оставшиеся элементы и сам стек.

Ваша программа получит на вход:

Количество операций.
Каждую операцию на отдельной строке (push X, pop или peek).

Пример вывода, если на вход подано 5, а затем push 10, push 20, peek, pop, pop:

20
20
10

Пример вывода, если на вход подано 3, а затем pop, push 42, peek:

empty
42

Пример вывода, если на вход подано 4, а затем push 5, push 15, pop, pop:

15
5

Помните, что ваш стек хранит указатели void* — вызывающая сторона несет ответственность за выделение и освобождение фактических данных. При извлечении (pop) приводите возвращаемый void* обратно к int*, чтобы получить доступ к значению. Используйте strcmp из <string.h> для сравнения строк команд.

Попробуйте сами

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: Создать стек емкостью 10
    
    // TODO: Обработать каждую операцию
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: Выделить память под целое число в куче и поместить указатель на него в стек
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Извлечь элемент из стека
            // - Если не NULL, вывести значение и освободить память из-под целого числа
            // - Если NULL (пустой стек), вывести "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Посмотреть верхний элемент
            // - Если не NULL, вывести значение (не удалять и не освобождать память)
            // - Если NULL (пустой стек), вывести "empty"
        }
    }
    
    // TODO: Освободить все оставшиеся элементы в стеке
    // TODO: Освободить сам стек
    
    return 0;
}