Stack (datastruktur)

Från Wikipedia
Hoppa till navigering Hoppa till sök

Stack (engelska för stapel) är en ordnad följd av dataelement där det senast inkomna elementet bearbetas först. Principen som strukturen följer är "sist in, först ut", på engelska "last-in, first out" (LIFO). De operationer som finns är lägga på (engelska: push) och lyfta av (engelska: pop).[1]

Stack med operationerna push och pop.

Stacken kan liknas med en tallriksstapel som kan påträffas i en skolbespisning eller lunchrestaurang. På stapeln kan man endast lägga en tallrik eller ta bort den översta. Tallrikar inne i stapeln kan inte kommas åt utan att ovanpåliggande tallrikar först tas bort. För att till exempel byta ut den tionde tallriken räknat uppifrån avlägsnar man alltså först var och en av de nio översta, så att tallrik tio ligger fri. Sen gör man tallriksbytet och avslutar genom att i ordning lägga tillbaka de nio man tog bort.

Stacken är en mycket vanlig datastruktur och används implicit i stort sett i alla datorprogram. Vid funktionsanrop i imperativa programspråk lagras anropsparametrarna och lokala variabler i en stack-struktur, så att de sedan kan hämtas tillbaka i rätt ordning när funktionen återvänder. Många processorer har en inbyggd stack för att hantera funktionsanrop och returadresser.

För att hålla reda på var i minnet det översta elementet i stacken finns används en stackpekare.

Se även[redigera | redigera wikitext]

Källor[redigera | redigera wikitext]

  1. ^ ”Term stack”. http://www.termado.com/DatatermSearch/?ss=array. Läst 16 november 2018.