Stack

Definition

En stack är en datastruktur där vi bara kan lägga in någonting överst och det enda vi kan hämta är det som sist lades in (kallas LIFO, Last In First Out). Ett bra exempel för att förstå stacken är en talrikshållare på en lunchrestaurang (se bilden på sid 31 i kompendiet).

En stack måste innehålla dessa två operationer:

push Placerar ett element överst på stacken, dvs ovanför det element som tidigare var överst.
precondition: ingen
postcondition: Det pushade elementet läggs in på stacken och är det element som kommer att returneras av en följande pop. Resten av stacken påverkas inte.
pop Returnerar det översta elementet (dvs det som sist lades in på stacken) och tar bort det från stacken. Elementet under är nu det översta och det som kommer att returneras vid nästa pop.
precondition: Stacken är inte tom.
postcondition: Det popade elementet är borta från stacken. För övrigt är stacken oförändrad.

Ytterligare några operationer stackar ofta har är dessa:

isEmpty Testar om stacken är tom. Eftersom denna operation ändå måste utföras varje gång pop exekveras kan vi lika gärna göra den tillgänglig för användaren som en operation i stackens gränssnitt.
precondition: ingen
postcondition: ingen
top Returnerar det översta elementet på stacken utan att ta bort det. Användaren kan i och för sig åstadkomma detta genom att göra pop följt av push men det blir mycket långsammare. Dessutom är operationen top väldigt öätt att implementera.
precondition: Stacken är inte tom
postcondition: Stacken är oförändrad.

Ytterligare exempel på möjliga operationer finns på sid 33 i kompendiet. Här är definitionen på den stack som används i exemplen nedan, stack.h .

Implementation

Alla sekvenser kan enkelt implementeras på två olika sätt, med en array eller med en länkad lista. Vi tar en titt på dessa två olika implementationer av en stack.

Array

Här är ett exempel där stacken är implementerad mha en array, ArrayStack.c , och här är ett enkelt program för att testa den, StackTest.c .

Det förefaller uppenbart att både push och pop tar O(1) tid, dvs de är oberoende av stackens storlek. Men vad händer om arrayen blir full? Då måste vi skapa en ny större array och kopiera över hela stacken dit. Låt oss anta att vi dubblar arrayens storlek varje gång den blir full. Detta innebär att en push som leder till dubbling tar O(n), där n är arrayens längd. Eftersom det är sämsta fallet (worst case) vi måste ta hänsyn till när vi beräknar prestanda skulle detta innebära att push tar O(n), vilket blir helt oacceptabelt. Det är dock inte så illa eftersom den push som ledde till arraydubbling måste föregås av n andra push som inte lett till dubbling. Detta innebär att vi kan sprida ut kostnaden för dubblingen över n olika anrop av push, exekveringshastigheten är alltså verkligen O(1).

Vad gäller minnesåtgång krävs endast plats för elementen. Observera dock att det kan ha allokerats mycket outnyttjat minnesutrymme för oanvända positioner i arrayen. Detta kan vara ett problem om varje element tar stor plats.

Länkad lista

Här är ett exempel där stacken är implementerad mha en länkad lista, ListStack.c . Den kan testas med samma program som ovan (pga abstraktion med hjälp av specifikation!!!).

Även med denna implementation exekveras push och pop på O(1) tid, dvs oberoende av stackens storlek. Detta innebär dock inte att exekveringshastigheten är identisk med arrayimplementationens. Som framgår av koden krävs i detta fall ett anrop av antingen new eller delete samt en del pekarhantering. Skillnaden är dock inte stor om vi tar hänsyn till arraydubblingen.

Vad gäller minnesutrymme går det åt utrymme för en pekare per element. Å andra sidan behöver vi aldrig reservera utrymme för fler element än det för ögonblicket finns.

Jämförelse

Implementationerna är tämligen likvärdiga.

Vad gäller konstruktion och underhåll är det ett tämligen enkelt och välkänt förfarande i båda fallen, kanske är arrayen lite lättare.
I fråga om exekveringshastigheten är arrayen lite bättre om stacken har tämligen konstant storlek. Då behövs inte arraydubbling särskilt ofta.
Den länkade listan är att föredra ur minnessynpunkt om varje element tar stor plats eller om vi har extremt ont om minne och inte vill allokera något outnyttjat minnesutrymme.

Exempel

Här är ett exempel på hur en stack kan användas, Parantes.c . Det finns på sid 34 i kompendiet.

Några finurligheter

Fler stackar samtidigt

Våra stackbibliotek ovan kan inte hantera mer än en stack. Hur ska vi kunna göra om dem så att de kan användas av program som behöver mer än en stack? Vi blir tvugna att skriva funktioner som skapar och tar bort hela stackar och eventuellt att hålla en array (eller länkad lista) med alla stackar. Dessutom måste vi utöka alla funktioner (push, pop osv) så att de tar en parameter som identifierar vilken stack operationen ska utföras på.

Sån't är livet med strukturerade språk. Snyggare lösningar är möjliga med objektorienterad programmering.

Godtycklig elementtyp

I stackbiblioteken vi skrev gick det bara att spara element av typen integer. De vore mycket mer användbara om det gick att spara element av vilken typ som helst. Det skulle vara en bättre, mer generell, abstraktion som inte gjorde något antagande om hur stacken skulle användas. Hur ska vi då ordna det? En lösning är den typiska c-varianten att låta stacken hantera void-pekare eller råa (otolkade) bytes och sedan spara en pekare till datat eller spara datat som råa bytes (tex mha en union).

En (ur programmeringssynpunkt) mycket bättre lösning (eftersom den är typsäker) är att över allt i stackbiblioteket definiera elementtypen som en egendefinierad typ och sedan ha en typdeklaration ev den. Här är ett exempel där arrayimplementationen är omgjord på det viset: stack.h , ArrayStack.c . Denna metod har dock den stora nackdelen att hela biblioteket (dvs filen ArrayStack.cc) måste kompileras om ifall vi byter typ på elementen.