Stakk (datastruktur)

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å 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.

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.