Stack (datastruktur)
Stacken är en av de viktigaste datastrukturerna inom datavetenskap. För att förstå hur en stapel fungerar kan du tänka dig en kortlek med spelkorten med framsidan nedåt. Vi kan bara enkelt komma åt det kort som ligger överst. När vi vill titta på det översta kortet kan vi göra två saker: vi kan titta på det, men låta det ligga kvar på stapeln, eller så kan vi ta bort det. När vi tar bort det översta föremålet tar vi bort det från stapeln. Om vi vill lägga till ytterligare ett kort på toppen av stapeln trycker vi på.
En stapel kallas LIFO-samling (last-in-first-out). Det betyder att det sista som läggs till (skjuts) är det första som tas bort (tas bort). Om det sista kortet vi lade på vår kortstapel var ett ess, är det första kortet vi tog bort från toppen samma ess.
Två åtgärder på en stapel: push och pop.
Historia
Stapeln föreslogs först 1955 och patenterades 1957 av tysken Friedrich L. Bauer. Samma koncept utvecklades oberoende, ungefär samtidigt, av australiensaren Charles Leonard Hamblin.
Andra åtgärder
I moderna datorspråk används stacken vanligtvis med fler operationer än bara "push" och "pop". Vissa implementeringar har en funktion som returnerar stackens aktuella längd. En annan typisk hjälpoperation är "top" (även känd som "peek"), som kan återge det aktuella översta elementet i stapeln utan att ta bort det. En annan vanlig operation är "dup", som gör en kopia av elementet högst upp på stapeln.
Relaterade sidor
- Stack-maskin
