Introduktion

Datastrukturer organiserar lagring i datorer så att vi effektivt kan få tillgång till och ändra data. Staplar och köer är några av de tidigaste datastrukturerna som definierats inom datavetenskapen.

De är enkla att lära sig och lätta att implementera, deras användningsområden är vanliga och du kommer troligen att finna dig själv att införliva dem i din mjukvara för olika uppgifter.

Det är vanligt att staplar och köer implementeras med en array eller länkad lista. Vi kommer att förlita oss på List datastrukturen för att rymma både stackar och köer.

Hur fungerar de?

Stack

Stackar följer, som namnet antyder, LIFO-principen (Last-in-First-Out). Som om man staplar mynt på varandra är det sista myntet vi lägger ovanpå det som först tas bort från stapeln senare.

För att implementera en stapel behöver vi därför två enkla operationer:

• push – lägger till ett element högst upp i stapeln:

• pop – tar bort elementet högst upp i stapeln:

Queueue

Queues, som namnet antyder, följer FIFO-principen (First-in-First-Out). Som om man står i en kö för biobiljetter: den som står först i kön är den första som köper en biljett och kan njuta av filmen.

För att implementera en kö behöver vi därför två enkla operationer:

• enqueue – lägger till ett element i slutet av kön:

• dequeue – tar bort elementet i början av kön:

Stackar och köer med hjälp av listor

Pythons inbyggda Listdatastruktur levereras med metoder för att simulera både stack- och köoperationer.

Låt oss betrakta en stapel med bokstäver:

Vi kan använda samma funktioner för att implementera en kö. Funktionen pop tar valfritt indexet för det objekt vi vill hämta som argument.

Så vi kan använda pop med det första indexet i listan, dvs. 0, för att få ett köliknande beteende.

Tänk på en ”kö” av frukter:

Även här använder vi listans append och pop-operationer för att simulera en kös kärnoperationer.

Staplar och köer med Deque-biblioteket

Python har ett deque (uttalas ’deck’) bibliotek som tillhandahåller en sekvens med effektiva metoder för att arbeta som en stapel eller en kö.

deque är en förkortning för Double Ended Queue – en generaliserad kö som kan hämta det första eller sista elementet som lagras:

Om du vill lära dig mer om deque-biblioteket och andra typer av samlingar som Python tillhandahåller kan du läsa vår artikel Introduction to Python’s Collections Module.

Stricter Implementations in Python

Om din kod behövde en stapel och du tillhandahåller en List finns det inget som hindrar en programmerare från att anropa insert, remove eller andra listfunktioner som påverkar ordningen på din stapel! Detta förstör i grunden poängen med att definiera en stapel, eftersom den inte längre fungerar som den ska.

Det finns tillfällen då vi vill försäkra oss om att endast giltiga operationer kan utföras på våra data.

Vi kan skapa klasser som endast exponerar de nödvändiga metoderna för varje datastruktur.

För att göra detta skapar vi en ny fil som heter stack_queue.py och definierar två klasser:

De programmerare som använder våra Stack och Queue uppmuntras nu att använda de tillhandahållna metoderna för att manipulera data istället.

Exempel

Föreställ dig att du är en utvecklare som arbetar med en helt ny ordbehandlare. Du har till uppgift att skapa en ångra-funktion – så att användarna kan spåra sina handlingar tillbaka till början av sessionen.

En stack passar utmärkt för detta scenario. Vi kan registrera varje åtgärd som användaren gör genom att skjuta den till stapeln. När användaren vill ångra en åtgärd tar han upp den från stapeln. Vi kan snabbt simulera funktionen så här:

Köer har också utbredda användningsområden inom programmering. Tänk på spel som Street Fighter eller Super Smash Brothers. Spelare i dessa spel kan utföra speciella rörelser genom att trycka på en kombination av knappar. Dessa knappkombinationer kan lagras i en kö.

Föreställ dig nu att du är en utvecklare som arbetar med ett nytt fightingspel. I ditt spel utlöses en ingångshändelse varje gång en knapp trycks ned. En testare märkte att om knapparna trycks in för snabbt så bearbetar spelet bara den första och specialmoves fungerar inte!

Du kan åtgärda det med en kö. Vi kan ställa alla inmatningshändelser i kö när de kommer in. På så sätt spelar det ingen roll om inmatningshändelser kommer med kort tid mellan dem, de kommer alla att lagras och vara tillgängliga för bearbetning. När vi har bearbetat rörelserna kan vi ta bort dem från kön. Ett speciellt drag kan arbetas ut så här:

Slutsats

Stackar och köer är enkla datastrukturer som gör det möjligt för oss att lagra och hämta data sekventiellt. I en stapel är det sista objektet vi lägger in det första som kommer ut. I en kö är det första objektet vi matar in det första som kommer ut.

Vi kan lägga till objekt till en stapel med hjälp av operationen push och hämta objekt med hjälp av operationen pop. Med köer kan vi lägga till objekt med hjälp av operationen enqueue och hämta objekt med hjälp av operationen dequeue.

I Python kan vi implementera stackar och köer bara genom att använda den inbyggda datastrukturen List. Python har också biblioteket deque som effektivt kan tillhandahålla stack- och köoperationer i ett objekt. Slutligen har vi gjort våra stack- och köklasser för bättre kontroll av våra data.

Det finns många användningsområden för stackar och köer i den verkliga världen, om vi förstår dem kan vi lösa många problem med datalagring på ett enkelt och effektivt sätt.