introduktion
datastrukturer organiserer lagring i computere, så vi effektivt kan få adgang til og ændre data. Stakke og køer er nogle af de tidligste datastrukturer defineret i datalogi.
enkel at lære og nem at implementere, deres anvendelser er almindelige, og du vil sandsynligvis finde dig selv at indarbejde dem i dit program til forskellige opgaver.
det er almindeligt, at stakke og køer implementeres med et Array eller en sammenkædet liste. Vi vil stole på List datastruktur for at rumme både stakke og køer.
Hvordan virker de?
stak
stakke, som navnet antyder, følg last-in-First-Out (LIFO) – princippet. Som om stabling af mønter oven på hinanden, er den sidste mønt, vi lægger på toppen, den, der er den første, der fjernes fra stakken senere.
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:
kø
køer, som navnet antyder, følger FIFO-princippet (first-in-first-out). Som om man venter i kø for filmbilletterne, er den første til at stå i kø den første til at købe en billet og nyde filmen.
for at implementere en kø har vi derfor brug for to enkle operationer:
-
enqueue– tilføjer et element til slutningen af køen:
-
dequeue– fjerner elementet i begyndelsen af køen:
stakke og køer ved hjælp af lister
Pythons indbyggede List datastruktur leveres sammen med metoder til at simulere både stak-og køoperationer.
lad os overveje en stak bogstaver:
Vi kan bruge de samme funktioner til at implementere en kø. Funktionenpop tager eventuelt indekset for det emne, vi vil hente som et argument.
så vi kan bruge popmed det første indeks på listen, dvs. 0, for at få kølignende opførsel.
overvej en “kø” af frugter:
igen, her bruger viappend ogpop operationer på listen for at simulere kerneoperationerne i en kø.
stakke og køer med Dekebiblioteket
Python har etdeque (udtales ‘deck’) bibliotek, der giver en sekvens med effektive metoder til at arbejde som en stak eller en kø.
deque er en forkortelse for Double Ended kø – en generaliseret kø, der kan få det første eller sidste element, der er gemt:
Hvis du gerne vil lære mere omdeque bibliotek og andre typer samlinger Python giver, kan du læse vores Introduktion til Pythons samlinger Modulartikel.
strengere implementeringer i Python
Hvis din kode havde brug for en stak, og du giver en List, er der intet, der forhindrer en programmør i at ringeinsertremove eller andre listefunktioner, der vil påvirke rækkefølgen af din stak! Dette ødelægger grundlæggende punktet med at definere en stak, da den ikke længere fungerer som den skal.
der er tidspunkter, hvor vi gerne vil sikre, at kun gyldige handlinger kan udføres på vores data.
Vi kan oprette klasser, der kun udsætter de nødvendige metoder til hver datastruktur.
for at gøre det, lad os oprette en ny fil kaldet stack_queue.py og definere to klasser:
programmørerne bruger vores Stackog Queue opfordres nu til at bruge de metoder, der leveres til at manipulere dataene i stedet.
eksempler
Forestil dig, at du er en udvikler, der arbejder på en helt ny tekstbehandler. Du har til opgave at oprette en fortryd – funktion-så brugerne kan backtrack deres handlinger indtil begyndelsen af sessionen.
en stak er en ideel pasform til dette scenario. Vi kan registrere hver handling brugeren tager ved at skubbe den til stakken. Når brugeren ønsker at fortryde en handling, de vil pop det fra stakken. Vi kan hurtigt simulere funktionen som denne:
køer har også udbredt anvendelse i programmering. Tænk på spil som Street Fighter eller Super Smash Brothers. Spillere i disse spil kan udføre særlige træk 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, hver gang der trykkes på en knap, en input begivenhed er fyret. En tester bemærkede, at hvis der trykkes for hurtigt på knapperne, behandler spillet kun den første, og specielle bevægelser fungerer ikke!
Du kan rette det med en kø. Vi kan forespørge alle inputbegivenheder, når de kommer ind. På denne måde betyder det ikke noget, om inputhændelser kommer med lidt tid mellem dem, de gemmes alle og er tilgængelige til behandling. Når vi behandler bevægelserne, kan vi afkø dem. Et specielt træk kan udarbejdes som dette:
konklusion
stakke og køer er enkle datastrukturer, der giver os mulighed for at gemme og hente data sekventielt. I en stak er det sidste element, vi indtaster, det første, der kommer ud. 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 operation og hente elementer ved hjælp af pop operation. Med køer tilføjer vi elementer ved hjælp af enqueue drift og hente elementer ved hjælp af dequeue operation.
i Python kan vi implementere stakke og køer bare ved at bruge den indbyggedeList datastruktur. Python har ogsådeque biblioteket, som effektivt kan levere stak-og køoperationer i et objekt. Endelig har vi lavet vores stack og kø klasser for strammere kontrol over vores data.
der er mange brugssager i den virkelige verden til stakke og køer, hvis vi forstår dem, kan vi løse mange datalagringsproblemer på en nem og effektiv måde.