Stack (datastruktur) – LIFO: definition, push/pop och exempel

Lär dig stacken (LIFO): tydlig definition, push/pop-operationer och praktiska exempel för effektiv programmering och algoritmer — för nybörjare och erfarna utvecklare.

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: du kan endast enkelt komma åt det kort som ligger överst. När du vill titta på det översta kortet kan du antingen låta det ligga kvar på stapeln (titta utan att ta bort) eller ta bort det. När du tar bort det översta föremålet tas det bort från stapeln. Om du vill lägga till ytterligare ett kort på toppen av stapeln placerar du det överst.

En stapel kallas en LIFO-samling (Last-In, First-Out). Det betyder att det sista elementet som läggs till (pushas) är det första som tas bort (poppas). Om det sista kortet du lade på kortstapeln var ett ess, är det esset du först tar bort från toppen.

Grundläggande operationer

• push(x) — lägg till elementet x överst på stacken.
• pop() — ta bort och returnera det översta elementet. Ofta ger pop ett fel eller undantag om stacken är tom.
• peek() / top() — läs av det översta elementet utan att ta bort det.
• isEmpty() — kontrollera om stacken är tom.
• size() — returnera antalet element i stacken.

Implementeringar

Stackar är enkla att implementera och kan byggas på flera sätt:

• Array (fält) — en vanlig implementation där en pekare håller reda på toppen. Vid behov kan fältet göras dynamiskt (t.ex. through resizing) för att tillåta obegränsad tillväxt.
• Enkel länkad lista — nya noder läggs till och tas bort i listans huvud (head), vilket gör push och pop enkla och effektiva utan att behöva kopiera element vid resize.

Vilken implementation som är bäst beror på språk, minneshantering och om du behöver en begränsad (fixed-capacity) eller obegränsad stack.

Tids- och rymdkomplexitet

• Push och pop är vanligen O(1) — de görs i konstant tid.
• Peek/isEmpty/size är också O(1).
• Rymdkomplexitet är O(n) där n är antal element i stacken. Vid användning av dynamiska arrayer kan resize-operationer ibland ge enstaka O(n)-kostnader, men amortiserad tid för push förblir O(1).

Enkelt exempel (logiskt)

Anta att stacken är tom. Vi gör följande operationer:

• push(1) → stack: [1]
• push(2) → stack: [1, 2]
• push(3) → stack: [1, 2, 3] (3 är överst)
• pop() → returnerar 3 → stack blir [1, 2]
• peek() → returnerar 2, stack förblir [1, 2]

En kort pseudokod för push och pop:

 push(x):   top = top + 1   data[top] = x  pop():   if top == -1:     error "stack underflow"   x = data[top]   top = top - 1   return x 

Användningsområden

• Funktionsanrop och returvärden (körstacken i många språk).
• Rekursion: implementeras ofta med en stack under ytan.
• Uttrycksevaluering och parantesmatchning (t.ex. infix → postfix).
• Ångra/återställ-funktionalitet i applikationer (undo/redo).
• Sökalgoritmer som depth-first search (DFS) och backtracking.
• Webbläsarhistorik (tillbaka/framåt kan modelleras med stackar).

Begränsningar och variationer

• Stacken ger endast åtkomst till ett ställe (toppen); för sekventiell åtkomst eller köbeteende används andra strukturer (t.ex. köer = FIFO).
• Trådsäkerhet: i flertrådade miljöer krävs synkronisering eller atomära operationer för att undvika race conditions.
• Varianter: begränsade (fixed-size) stackar, dynamiska stackar, samt specialiserade staplar som flera stackar i en array.

Sammantaget är stacken en enkel men kraftfull datastruktur med bred användning i både algoritmer och praktiska program. Dess LIFO-egenskap (last-in, first-out) gör den särskilt lämpad när senaste tillagda elementet måste bearbetas först.

Sök med bokstav