Stak (datastruktur)
Stakken er en af de vigtigste datastrukturer inden for datalogi. For at forstå, hvordan en stak fungerer, skal du tænke på et spil kort med billedsiden nedad. Vi kan kun nemt få adgang til det kort, der ligger øverst. Når vi ønsker at se på det øverste kort, er der to ting, vi kan gøre: Vi kan kigge på det, men lade det blive på stakken, eller vi kan tage det af. Når vi tager det øverste objekt af, tager vi det af stakken. Hvis vi ønsker at tilføje et andet kort til toppen af stakken, skubber vi det.
En stak kaldes en LIFO-samling (last-in-first-out). Det betyder, at den sidste ting, der er tilføjet (pushed), er den første ting, der bliver trukket (popped) ud. Hvis det sidste kort, vi lagde på vores stak af kort, var et es, er det første kort, vi trak fra toppen, det samme es.
To handlinger på en stak: push og pop.
Historie
Stakken blev først foreslået i 1955 og derefter patenteret i 1957 af tyskeren Friedrich L. Bauer. Det samme koncept blev udviklet uafhængigt af hinanden på omtrent samme tidspunkt af australieren Charles Leonard Hamblin.
Andre operationer
I moderne computersprog er stakken normalt implementeret med flere operationer end blot "push" og "pop". Nogle implementeringer har en funktion, som returnerer stakkens aktuelle længde. En anden typisk hjælpeoperation er "top" (også kendt som "peek"), som kan returnere det aktuelle øverste element i stakken uden at fjerne det. En anden almindelig operation er "dup", som laver en kopi af elementet øverst på stakken.
Relaterede sider
- Stack maskine
