Redigerer Stakk (datastruktur)

{{kildeløs}}
En '''stakk''' (engelsk: '''stack'''), eller '''stabel''', er en abstrakt datastruktur for midlertidig lagring av data, objekter eller hendelser som tas ut én etter én basert på [[Last In First Out (databehandling)|sist-inn-først-ut]]-prinsippet. Stakker brukes i stor grad på alle nivåer i moderne datasystemer. For eksempel er dataprogrammer avhengige av en stakk for å håndtere funksjonskall.

== Operatorer ==
En stack har vanligvis to operatorer, ''push'' og ''pop''. Push operatoren legger et nytt element til øverst på stacken, mens pop tar det øverste elementet av stacken. Det er litt forskjellig fra implementasjon til implementasjon hvorvidt pop også returnerer verdien til elementet den tar av eller ikke, og hvordan den opptrer er gitt av hvilke andre operasjoner som finnes.

Andre vanlige operasjoner er ''peek'' og ''size''. Peek returnerer det øverste elementet uten å fjerne det. Hvis det finnes en ''peek'', så kan ''pop'' være kalt ''drop''. Size returnerer vanligvis antallet elementer i stakken, men kan også angi størrelsen i bytes. Hvis ''size'' angir størrelsen i bytes, så kan det finnes en operasjon ''length''.

== Eksempel på implementasjon ==
Under vises en naiv implementasjon av en stack skrevet i [[C_(programmeringsspråk)|C]].

Først definererer vi selve datatypen:
 #define MAX_STACK_ELEMENTS 10
 
 struct stack
 {
    int num_elements;
    int elements[MAX_STACK_ELEMENTS];
 };
 
 struct stack my_stack;
For enkelhets skyld har vi laget en stacktype med en fast størrelse på maks 10 elementer. Vi deklarerer også en lokal variabel ''my_stack'' som inneholder selve stacken.

Vi trenger en metode for å legge data på toppen av stacken:
 void push(int element)
 {
    if (my_stack.num_elements < MAX_STACK_ELEMENTS)
    {
        my_stack.elements[my_stack.num_elements] = element;
        my_stack.num_elements++;
    }
    else
    {
        printf("Stack overflow!\n");
    }
 }
Og en metode for å ta elementer av stacken:
 int pop()
 {
    if (my_stack.num_elements > 0)
    {
        my_stack.num_elements--;
        return my_stack.elements[my_stack.num_elements];
    }
    else
    {
        printf("Stack underflow!\n");
    }
 }

== Eksempel på bruk ==
Gitt stack implementasjonen over kan vi bruke stacken på følgende måte:
 push(2);
 push(5);
 push(6);
     
 assert(pop() == 6);
 assert(pop() == 5);
 assert(pop() == 2);
Legg merke til at vi forventer å få elementene ut i motsatt rekkefølge av hva vi legger dem inn i.

{{Autoritetsdata}}

[[Kategori:Dataterminologi]]
[[Kategori:Datastrukturer]]