Implementer en stabel i C: En komplett guide med kodeeksempler

0 Shares

En stakk, ofte referert til som en stack, er en grunnleggende datastruktur som opererer etter prinsippet «sist inn, først ut» (LIFO). Dette betyr at det siste elementet som legges til stakken, er det første som fjernes. Stakker er essensielle for en rekke databehandlingsoppgaver, inkludert håndtering av rekursive funksjoner, analyse av matematiske uttrykk og implementering av funksjoner som «tilbake»-knapper i brukergrensesnitt.

Denne veiledningen vil lede deg gjennom prosessen med å lage en stakk i programmeringsspråket C. Vi vil se på de viktigste prinsippene, gi kodeeksempler og utforske praktiske bruksområder for denne strukturen.

Grunnleggende konsepter

Stakkoperasjoner

Push: Legger til et nytt element på toppen av stakken.
Pop: Fjerner og returnerer det øverste elementet i stakken.
Topp (Peek): Returnerer det øverste elementet i stakken uten å fjerne det.
ErTom (Empty): Sjekker om stakken er tom.

Stakkrepresentasjon

I C kan en stakk representeres ved hjelp av en array eller en lenket liste. I denne artikkelen vil vi fokusere på bruken av en array.

Implementering av en stakk

Kodeeksempel

        
#include <stdio.h>
#include <stdlib.h>

#define MAKS_STØRRELSE 100

// Stakkstruktur
typedef struct {
    int topp;
    int elementer[MAKS_STØRRELSE];
} Stakk;

// Funksjon for å opprette en ny stakk
Stakk* lagNyStakk() {
    Stakk* stakk = (Stakk*) malloc(sizeof(Stakk));
    if (stakk == NULL) {
        fprintf(stderr, "Feil ved allokering av minne\n");
        exit(EXIT_FAILURE);
    }
    stakk->topp = -1;
    return stakk;
}

// Funksjon for å sjekke om stakken er tom
int erTom(Stakk* stakk) {
    return stakk->topp == -1;
}

// Funksjon for å hente antall elementer i stakken
int stakkStørrelse(Stakk* stakk) {
    return stakk->topp + 1;
}

// Funksjon for å returnere det øverste elementet uten å fjerne det
int peek(Stakk* stakk) {
    if (!erTom(stakk)) {
        return stakk->elementer[stakk->topp];
    } else {
        fprintf(stderr, "Stakken er tom!\n");
        exit(EXIT_FAILURE);
    }
}

// Funksjon for å fjerne og returnere det øverste elementet
int pop(Stakk* stakk) {
    if (!erTom(stakk)) {
        return stakk->elementer[stakk->topp--];
    } else {
        fprintf(stderr, "Stakken er tom!\n");
        exit(EXIT_FAILURE);
    }
}

// Funksjon for å legge til et nytt element i stakken
void push(Stakk* stakk, int element) {
    if (stakk->topp < MAKS_STØRRELSE - 1) {
        stakk->elementer[++stakk->topp] = element;
    } else {
        fprintf(stderr, "Stakken er full!\n");
    }
}

int main() {
    Stakk* stakk = lagNyStakk();

    push(stakk, 10);
    push(stakk, 20);
    push(stakk, 30);

    printf("Øverste element: %d\n", peek(stakk));
    printf("Fjernet element: %d\n", pop(stakk));
    printf("Fjernet element: %d\n", pop(stakk));
    printf("Fjernet element: %d\n", pop(stakk));


    if (erTom(stakk)) {
        printf("Stakken er tom.\n");
    }

    free(stakk);
    return 0;
}

Gjennomgang av koden

Vi definerer en Stakk-struktur, som inneholder en heltallsvariabel topp for å indikere toppen av stakken og et array elementer for å lagre data.
Funksjoner som lagNyStakk() og erTom() brukes for å initialisere stakken og kontrollere om den er tom.
Operasjonene push() og pop() håndterer innsetting og fjerning av elementer fra stakken.
peek() returnerer det øverste elementet uten å endre stakken, og stakkStørrelse() gir det gjeldende antallet elementer.

Praktiske bruksområder for stakker

Rekursive funksjoner

Stakker er sentrale i implementeringen av rekursive funksjoner, som beregning av fakultet eller traversering av binære trær. De lagrer konteksten for hvert funksjonskall, slik at programmet kan fortsette der det slapp etter et rekursivt kall.

Analyse av uttrykk

Stakker er svært nyttige for å evaluere postfix- og prefiksuttrykk. Operander legges på stakken, og når en operator påtreffes, utføres operasjonen, og resultatet legges tilbake på stakken, noe som til slutt resulterer i det endelige svaret.

«Tilbake»-funksjoner

I grafiske brukergrensesnitt (GUI) brukes stakker ofte for å implementere «tilbake»-knapper. Hver gang brukeren navigerer til en ny side eller skjerm, legges den gjeldende tilstanden til stakken. Når brukeren trykker «tilbake», hentes den forrige tilstanden fra stakken.

Konklusjon

Å implementere en stakk i C er en verdifull programmeringsferdighet. Det gir en effektiv metode for å administrere data basert på LIFO-prinsippet, og har mange viktige bruksområder i databehandling. Gjennom denne artikkelen har vi dekket de grunnleggende prinsippene, demonstrert hvordan man implementerer en stakk i C, og utforsket ulike bruksområder. En god forståelse av stakker vil forbedre din evne til å skrive effektiv og robust kode.

Ofte stilte spørsmål

Hva er forskjellen mellom en stakk og en kø?
En stakk følger LIFO-prinsippet, mens en kø (queue) følger FIFO-prinsippet (først inn, først ut). Stakker er ideelle når du trenger å behandle elementer i motsatt rekkefølge av hvordan de ble lagt til.
Hvordan setter jeg en grense for størrelsen på stakken?
Du kan kontrollere stakkens størrelse ved å legge til en sjekk i push()-operasjonen: if (stakk->topp < MAKS_STØRRELSE - 1).
Hva skjer hvis jeg prøver å fjerne et element fra en tom stakk?
Forsøk på å fjerne et element fra en tom stakk vil føre til en feil. Du bør sjekke at stakken ikke er tom før du fjerner elementer.
Kan jeg bruke en lenket liste for å implementere en stakk?
Ja, en stakk kan implementeres ved hjelp av en lenket liste, som tillater dynamisk endring av stakkens størrelse.
Hvilke programmeringsspråk støtter stakker?
De fleste programmeringsspråk, inkludert C, C++, Java, Python og JavaScript, støtter implementasjon av stakker.
Er det effektivt å bruke stakker i C?
Ja, implementering av stakker i C er effektivt og utnytter C’s minnehåndteringsfunksjoner.
Kan en stakk brukes til å lage en kø?
Ja, en kø kan implementeres ved bruk av to stakker. En stakk brukes for innsetting, og den andre for fjerning.
Er stakker egnet for parallellprogrammering?
Stakker er generelt ikke egnet for parallellprogrammering, da de ikke er trådsikre. Samtidig tilgang til en stakk fra flere tråder kan føre til datakorrupsjon.