Stakk (datastruktur)

Fra Wikipedia, den frie encyklopedi

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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.