Stack (datastruktur)
Stack eller LIFO (Last In, First Out), en linjär datastruktur med två operationer: push och pop (ibland kallas operationen pull). Push lägger in ett element överst på stacken, och pop tar bort det översta elementet. Namnet "stack" kommer från engelskan och betyder "hög" eller "stapel".
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 t ex 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.
Av effektivitetsskäl kan en stack berikas med stackpekare som medger direktåtkomst till tallrikar i stapelns mitt utan att ovanpåliggande behöver avlägsnas/återställas.
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 stackstruktur, 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.
Se även
