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

Часть раздела Объектно-ориентированное программирование путешествия по C на Coddy. Урок 60 из 61.

Задание

Легко

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

Давай создадим Generic Stack: универсальную структуру данных, способную хранить данные любого типа с использованием указателей void*. Твой стек будет следовать принципу Last-In-First-Out и поддерживать все основные операции.

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

stack.h: Define структуру Stack с тремя членами: массив void** для элементов, int для индекса вершины (следующая свободная позиция) и int для capacity. Declare прототипы function для создания стека (принимает capacity), добавления элемента, удаления элемента, просмотра верхнего элемента, проверки, пуст ли стек, и освобождения стека.
stack.c: Implement свой обобщённый стек:
- create_stack: выделяет Stack в heap, выделяет массив items с given capacity, инициализирует top значением 0 и возвращает указатель
- push: добавляет элемент на вершину, если есть место (когда top меньше capacity)
- pop: удаляет и возвращает верхний элемент или возвращает NULL, если стек empty
- peek: возвращает верхний элемент, не удаляя его, или NULL, если стек empty
- is_empty: возвращает 1, если в стеке нет элементов, и 0 в противном случае
- free_stack: сначала освобождает массив items, а затем саму структуру Stack
main.c: Считай количество выполняемых операций. Затем для каждой operation считай command: push, за которым следует целое значение, pop или peek. Create стек с capacity 10. Для push выдели integer в heap и добавь его pointer. Для pop получи item, выведи его значение и освободи integer. Для peek выведи значение, не удаляя его. Если pop или peek вызывается для empty стека, выведи empty. После выполнения всех операций освободи все оставшиеся items и стек.

Твоя программа получит:

Количество операций
Каждую operation в отдельной строке (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*: вызывающая сторона отвечает за выделение и освобождение фактических данных. При извлечении выполни приведение возвращённого void* обратно к int*, чтобы получить доступ к значению. Используй strcmp из <string.h> для сравнения строк command.

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

#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;
}