Start | stack
 

Stack



En stack fungerar som en hög tallrikar. Det vi lägger till hamnar överst, men det är också från toppen vi plockar. Man kallar det ibland för LIFO (last-in first-out).

Som en hög tallrikar

Tänk dig en hög med tallrikar på en restaurang. Diskade tallrikar fylls på ovanifrån. Gäster i restaurangen plockar också tallrikar ovanifrån. Om det diskas fler tallrikar än det finns gäster, så växer stacken med tallrikar. Om gästerna är fler än vad som diskas, så krymper stacken.

Push och Pop


Det finns 2 operationer på en stack. Push när du placerar ett element på stacken och pop när du hämtar ett element.



Push

Push fyller på överst. Så, vi definierar funktionen push(objekt) som placerar ett objekt överst på stacken. Det kan i princip vara vad som helst, det har ingen betydelse för själva konceptet med stack. Det kan vara ett heltal, det kan vara ett objekt.

Enklaste implementationen av en stack är att använda de metoder som redan finns på en lista. Som push använder vi append, den gör samma sak.
stack = [] stack.append(10) print(stack) stack.append(15) print(stack) stack.append(6) print(stack)

Pop

Pop är då att vi plockar bort det översta på stacken - och läser samtidigt av dess värde.

Pop finns faktiskt som funktion på vår lista.
stack = [] stack.append(10) print(stack) stack.append(15) print(stack) stack.append(6) print(stack) print(stack.pop()) print(stack.pop()) print(stack.pop())

Peek

Peek är en funktion som brukar finnas där man kan läsa av värdet på stackens översta objekt - utan att röra det. Dvs, utan att göra pop. Lite som om du tänker dig restaurangen, så tittar du på den översta tallriken och dubbelkollar att den är ren.

Om vi vill titta på det "översta" elementet i vår lista, så kan vi titta på stack[-1], dvs vi läser det sista elemntet i listan bakifrån.
stack = [] stack.append(10) print(stack) stack.append(15) print(stack) stack.append(6) print(stack) print(stack[-1]) print(stack.pop()) print(stack[-1]) print(stack.pop()) print(stack.pop())

används till?

Undo


Tänk dig en applikation, ordbehandling, bild, vad som helst. I programmet finns en undo -funktion. Det är implementerat som en stack. Varje gång du gör något, klickar ett tecken på tangentbordet, drar en linje, suddar, färglägger, så placeras manövern samtidigt på stacken. På så vis kan du när som helst klicka på undo och programmet tar då och gör pop på stacken, läser av vad du gjorde, och gör detta ogjort. Om det överst på stacken står att du klickade på knappen "E", så kommer "E" tas bort. Klickar du undo igen, så gör programmet pop en gång till och gör ogjort det som numera ligger överst på stacken.

Funktionsanrop


I datorprogram, på lägre nivå, maskinkod eller bytekod, där placerar man funktionens argument på stacken innan anrop och sedan kommer funktionen ifråga att placera sitt returvärde på stacken. Den anropade funktionen placerar alltså argument på stacken och när funktionen returnerar så ligger returvärdet på stacken. Detta gör det möjligt för funktioner att kunna anropas i funktioner och alla kan jobba på samma sätt med argument och returvärde.

Olika algoritmer


Algoritmer av rekursiv natur (anropar sig själv) eller algoritmer där en ommöblering av data har en rekursiv natur, t.ex. konvertera infix notation till postfix, dvs med hänsyn till ett matematiskt uttrycks prioriteringsregler (multiplikation före addition, parenteser före multiplikation osv.) skapa en stack där det med högst prioritet ligger överst så att det blir enkelt räkna ut.

Skapa en stack

Säg, att vi skulle skapa en stack som en class. Vi kan då bygga en "överrock" på vår lista så att den blir lite mer officiell och representativ.

__init___


Init (klassens konstruktor) initierar själva klassen, i detta fall sätter den en lista att vara tom från början.

__len___


Tack vara len kan vi kolla storleken på stacken. Det kan ibland vara intressant veta om det är tom.

__str___


Med str kan vi skriva ut stacken.

push


Push gör helt enkelt append på vår lista, vilket är samma sak. Man villdock att det skall heta push.

pop


Pop() plockar senast append:ade objekt. Pop går att anropa med ett argument, t.ex. kommer pop(0) plocka första elementet i listan (vilket inte är vad vi vill). Att anropa pop() utan argumentär medvetet för att få sista elementet i listan.

peek


Peek smygtittar på senaste elementet. Det är käckt med python eftersom vi kan läsa en lista bakifrån, för att läsa sist ditlagda element.
class Stack: def __init__(self): self.lst = [] def __len__(self): return(len(self.lst)) def __str__(self): return(str(self.lst)) def push(self,obj): self.lst.append(obj) def pop(self): return self.lst.pop() def peek(self): if(len(self.lst)==0): return None else: return(self.lst[-1]) stack = Stack() print(stack) stack.push(10) print(stack) stack.push(20) print(stack) stack.push(3.14) print(stack) print("stackens storlek=",len(stack)) print(stack.peek()) print(stack.pop()) print(stack.pop()) print(stack.pop()) print("stackens storlek=",len(stack)) print(stack.peek())
14.952182769775 ms