Stos generyczny

Część sekcji Programowanie obiektowe ścieżki C w Coddy. Lekcja 60 z 61.

Wyzwanie

Łatwy

Stos to podstawowa struktura danych działająca zgodnie z zasadą Last-In-First-Out (LIFO): ostatni dodany element jest pierwszym usuwanym. Wyobraź sobie stos talerzy: dodajesz je na górze i zdejmujesz z góry.

Zbudujmy stos generyczny: wszechstronną strukturę danych, która może przechowywać dowolny typ danych za pomocą wskaźników void*. Twój stos będzie działać zgodnie z zasadą Last-In-First-Out i będzie mieć wszystkie podstawowe operacje.

Rozmieścisz swój kod w trzech plikach:

stack.h: Zdefiniuj strukturę Stack z trzema polami: tablicą elementów typu void**, wartością typu int określającą indeks szczytu (następne wolne miejsce) oraz wartością typu int określającą pojemność. Zadeklaruj prototypy funkcji do tworzenia stosu (przyjmuje pojemność), dodawania elementu, zdejmowania elementu, podglądania elementu na szczycie, sprawdzania, czy stos jest pusty, oraz zwalniania stosu.
stack.c: Zaimplementuj swój stos generyczny:
- create_stack: alokuje stos na stercie, alokuje tablicę elementów o podanej pojemności, ustawia wartość top na 0 i zwraca wskaźnik
- push: dodaje element na szczycie, jeśli jest na to miejsce (gdy top jest mniejsze niż capacity)
- pop: usuwa i zwraca element ze szczytu albo zwraca NULL, jeśli stos jest pusty
- peek: zwraca element ze szczytu bez jego usuwania albo zwraca NULL, jeśli stos jest pusty
- is_empty: zwraca 1, jeśli stos nie zawiera elementów, a w przeciwnym razie 0
- free_stack: najpierw zwalnia tablicę elementów, a następnie samą strukturę Stack
main.c: Wczytaj liczbę operacji do wykonania. Następnie dla każdej operacji wczytaj polecenie: push, po którym następuje wartość całkowita, pop lub peek. Utwórz stos o pojemności 10. Dla push zaalokuj liczbę całkowitą na stercie i dodaj jej wskaźnik do stosu. Dla pop pobierz element, wyświetl jego wartość i zwolnij pamięć zajmowaną przez liczbę całkowitą. Dla peek wyświetl wartość bez usuwania elementu. Jeśli na pustym stosie zostanie wywołane pop lub peek, wyświetl empty. Po wykonaniu wszystkich operacji zwolnij pamięć zajmowaną przez pozostałe elementy i stos.

Twój program otrzyma:

Liczbę operacji
Każdą operację w osobnym wierszu (push X, pop lub peek)

Przykładowe wyjście dla danych wejściowych 5, a następnie push 10, push 20, peek, pop, pop:

20
20
10

Przykładowe wyjście dla danych wejściowych 3, a następnie pop, push 42, peek:

empty
42

Przykładowe wyjście dla danych wejściowych 4, a następnie push 5, push 15, pop, pop:

15
5

Pamiętaj, że twój stos przechowuje wskaźniki void*: to wywołujący odpowiada za alokowanie i zwalnianie pamięci na właściwe dane. Podczas zdejmowania elementu rzutuj zwrócony wskaźnik void* z powrotem na int*, aby uzyskać dostęp do wartości. Użyj funkcji strcmp z <string.h>, aby porównywać ciągi znaków poleceń.

Spróbuj swoich sił

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

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: Utwórz stos o pojemności 10
    
    // TODO: Przetwórz każdą operację
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: Przydziel pamięć na liczbę całkowitą na stercie i umieść wskaźnik do niej na stosie
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Zdejmij element ze stosu
            // - Jeśli nie jest NULL, wypisz wartość i zwolnij pamięć liczby całkowitej
            // - Jeśli jest NULL (pusty stos), wypisz "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Podejrzyj element na szczycie stosu
            // - Jeśli nie jest NULL, wypisz wartość (nie zdejmuj elementu ani nie zwalniaj jego pamięci)
            // - Jeśli jest NULL (pusty stos), wypisz "empty"
        }
    }
    
    // TODO: Zwolnij pamięć pozostałych elementów stosu
    // TODO: Zwolnij pamięć samego stosu
    
    return 0;
}

Wszystkie lekcje w sekcji Programowanie obiektowe

3Cykl życia obiektu

Wzorzec konstruktora Wzorzec destruktora Inicjalizacja na stosie Kopia głęboka Podsumowanie: klasa opakowująca ciąg znaków

6Dziedziczenie przez kompozycję

Osadzanie struktur Zasada pierwszego elementu Dostęp do elementów klasy nadrzędnej Konwersja w górę hierarchii Podsumowanie: hierarchia kształtów

9Projekt: Rysownik kształtów

Przegląd projektu Implementacja koła Implementacja prostokąta Zastosowanie polimorfizmu Kontener kształtów

12Wyzwania końcowe

Postać RPG Dynamiczne tworzenie ciągów znakówStos generycznySystem zdarzeń

Poćwicz samodzielnie: Kompilator C online