Indledning

Datastrukturer organiserer lagring af data i computere, så vi effektivt kan få adgang til og ændre data. Stakke og køer er nogle af de tidligste datastrukturer, der er defineret i datalogien.

Simpelt at lære og let at implementere, er deres anvendelser almindelige, og du vil højst sandsynligt finde dig selv indarbejde dem i din software til forskellige opgaver.

Det er almindeligt, at Stakke og køer implementeres med et Array eller en Linked List. Vi vil stole på List-datastrukturen til at rumme både Stacks og Queues.

Hvordan fungerer de?

Stack

Stacks følger, som navnet antyder, LIFO-princippet (Last-in-First-Out). Som hvis man stabler mønter oven på hinanden, er den sidste mønt, vi lægger øverst, den første, der senere skal fjernes fra stakken.

For at implementere en stak har vi derfor brug for to enkle operationer:

• push – tilføjer et element til toppen af stakken:

• pop – fjerner elementet øverst i stakken:

Queueue

Queues følger, som navnet antyder, FIFO-princippet (First-in-First-Out). Som hvis man står i en kø for at købe biografbilletter, er den første, der står i kø, den første, der køber en billet og kan nyde filmen.

For at implementere en kø har vi derfor brug for to enkle operationer:

• enqueue – tilføjer et element til enden af køen:

• dequeue – fjerner elementet i begyndelsen af køen:

Stakke og køer ved hjælp af lister

Pythons indbyggede List datastruktur er udstyret med metoder til at simulere både stak- og køoperationer.

Lad os betragte en stak af bogstaver:

Vi kan bruge de samme funktioner til at implementere en kø. Funktionen pop tager valgfrit indekset for det element, vi ønsker at hente, som et argument.

Så vi kan bruge pop med det første indeks i listen, dvs. 0, for at få kø-lignende adfærd.

Tænk på en “kø” af frugter:

Også her bruger vi append og pop-operationerne i listen til at simulere kerneoperationerne i en kø.

Stakke og køer med Deque-biblioteket

Python har et deque (udtales ‘deck’) bibliotek, der giver en række med effektive metoder til at arbejde som en stak eller en kø.

deque er en forkortelse for Double Ended Queue – en generaliseret kø, der kan hente det første eller sidste element, der er gemt:

Hvis du gerne vil lære mere om deque-biblioteket og andre typer samlinger, som Python tilbyder, kan du læse vores artikel Introduktion til Pythons samlingsmodul.

Stricter-implementeringer i Python

Hvis din kode havde brug for en stak, og du leverer en List, er der intet, der forhindrer en programmør i at kalde insert, remove eller andre listefunktioner, der vil påvirke rækkefølgen af din stak! Dette ødelægger grundlæggende pointen med at definere en stak, da den ikke længere fungerer som den skal.

Der er tidspunkter, hvor vi gerne vil sikre, at der kun kan udføres gyldige operationer på vores data.

Vi kan oprette klasser, der kun udsætter de nødvendige metoder for hver datastruktur.

Det gør vi ved at oprette en ny fil kaldet stack_queue.py og definere to klasser:

Programmørerne, der bruger vores Stack og Queue, opfordres nu til at bruge de udleverede metoder til at manipulere dataene i stedet.

Eksempler

Forestil dig, at du er en udvikler, der arbejder på et helt nyt tekstbehandlingsprogram. Du har til opgave at skabe en fortrydelsesfunktion – så brugerne kan gå tilbage til deres handlinger til begyndelsen af sessionen.

En stak passer perfekt til dette scenarie. Vi kan registrere hver handling, som brugeren foretager, ved at skubbe den til stakken. Når brugeren ønsker at fortryde en handling, popper de den fra stakken. Vi kan hurtigt simulere funktionen på følgende måde:

Queues har også udbredte anvendelser inden for programmering. Tænk på spil som Street Fighter eller Super Smash Brothers. Spillerne i disse spil kan udføre specielle bevægelser ved at trykke på en kombination af knapper. Disse knapkombinationer kan gemmes i en kø.

Forestil dig nu, at du er en udvikler, der arbejder på et nyt kampspil. I dit spil udløses der en inputbegivenhed, hver gang der trykkes på en knap. En tester har bemærket, at hvis der trykkes for hurtigt på knapperne, behandler spillet kun den første, og specielle bevægelser virker ikke!

Det kan du løse med en kø. Vi kan sætte alle input-hændelser i kø, efterhånden som de kommer ind. På denne måde er det ligegyldigt, om input events kommer med kort tid mellem dem, de vil alle blive gemt og være tilgængelige for behandling. Når vi er ved at behandle bevægelserne, kan vi fjerne dem fra køen. Et særligt træk kan udarbejdes på denne måde:

Konklusion

Stacks og køer er simple datastrukturer, der giver os mulighed for at lagre og hente data sekventielt. I en stak er det sidste element, vi indtaster, det første, der kommer ud som det første. I en kø er det første element, vi indtaster, det første, der kommer ud.

Vi kan tilføje elementer til en stak ved hjælp af push-operationen og hente elementer ved hjælp af pop-operationen. Med køer kan vi tilføje elementer ved hjælp af enqueue-operationen og hente elementer ved hjælp af dequeue-operationen.

I Python kan vi implementere stakke og køer blot ved at bruge den indbyggede List-datastruktur. Python har også deque-biblioteket, som effektivt kan levere stak- og køoperationer i ét objekt. Endelig har vi lavet vores stack- og kø-klasser for at opnå en strammere kontrol med vores data.

Der er mange virkelige anvendelsesmuligheder for stakke og køer, og ved at forstå dem kan vi løse mange datalagringsproblemer på en nem og effektiv måde.