Introduksjon
datastrukturer organiserer lagring i datamaskiner slik at vi effektivt kan få tilgang til og endre data. Stabler og Køer er noen av de tidligste datastrukturer definert i informatikk.Enkel å lære og enkel å implementere, deres bruk er vanlig, og du vil mest sannsynlig finne deg selv å innlemme dem i programvaren for ulike oppgaver.
Det er vanlig At Stabler og Køer implementeres med En Matrise eller Koblet Liste. Vi stoler påList datastruktur for å imøtekomme Både Stabler og Køer.
Hvordan Fungerer de?
Stack
Stabler, som navnet antyder, følger LIFO-prinsippet (LAST-In-First-Out). Som om stabling mynter oppå den andre, den siste mynten vi satt på toppen er den som er den første til å bli fjernet fra stabelen senere.
for å implementere en stabel trenger vi derfor to enkle operasjoner:
-
push– legger et element til toppen av stabelen:
pop– fjerner elementet øverst i stabelen:
Kø
køer, som navnet antyder, følger fifo-prinsippet (first-in-first-out). Som om du venter i kø for kinobilletter, den første til å stå i kø er den første til å kjøpe en billett og nyte filmen.
for å implementere en kø trenger vi derfor to enkle operasjoner:
-
enqueue– legger til et element i slutten av køen:
-
dequeue– fjerner elementet i begynnelsen av køen:
Stabler og Køer Ved Hjelp Av Lister
pythons innebygdeList datastruktur leveres med metoder for å simulere både stabel-og køoperasjoner.
la oss vurdere en bunke med bokstaver:
Vi kan bruke de samme funksjonene til å implementere En Kø. pop – funksjonen tar eventuelt indeksen til elementet vi vil hente som et argument.
så vi kan brukepop med den første indeksen i listen, dvs.0, for å få kølignende oppførsel.
Tenk på en «kø» av frukt:
Igjen, her bruker viappend ogpop operasjoner på listen for å simulere kjerneoperasjonene til en kø.
Stabler og Køer med Deque Biblioteket
Python har et deque (uttales ‘dekk’) bibliotek som gir en sekvens med effektive metoder for å fungere som en stabel eller en kø.
dequeer kort For Double Ended Queue – en generalisert kø som kan få det første eller siste elementet som er lagret:
hvis du vil lære mer omdeque bibliotek og andre typer samlinger Python gir, kan Du lese Vår Introduksjon Til Pythons Samlinger Modul artikkel.
Strengere Implementeringer I Python
hvis koden din trengte en stabel og du oppgir en List, er det ingenting som hindrer en programmerer fra å ringe insertremove eller andre listefunksjoner som vil påvirke rekkefølgen på stabelen din! Dette ødelegger fundamentalt poenget med å definere en stabel, da den ikke lenger fungerer som den skal.
det er tider når vi ønsker å sikre at bare gyldige operasjoner kan utføres på våre data.
Vi kan lage klasser som bare viser de nødvendige metodene for hver datastruktur.
for å gjøre det, la oss lage en ny fil kalt stack_queue.py og definere to klasser:
programmererne som bruker vår Stackog Queue oppfordres nå til å bruke metodene som tilbys for å manipulere dataene i stedet.
Eksempler
Tenk deg at du er en utvikler som jobber med en helt ny tekstbehandler. Du har til oppgave å opprette en angrefunksjon-slik at brukerne kan backtrack sine handlinger til begynnelsen av økten.
en stabel er en ideell passform for dette scenariet. Vi kan registrere hver handling brukeren tar ved å skyve den til bunken. Når brukeren ønsker å angre en handling, vil de pope den fra stakken. Vi kan raskt simulere funksjonen slik:
Køer har utbredt bruk i programmering også. Tenk på spill som Street Fighter eller Super Smash Brothers. Spillere i disse spillene kan utføre spesielle trekk ved å trykke på en kombinasjon av knapper. Disse knappekombinasjonene kan lagres i en kø.
forestill Deg nå at du er en utvikler som jobber med et nytt kampspill. I spillet ditt, hver gang en knapp trykkes, blir en inngangshendelse sparket. En tester la merke til at hvis knappene trykkes for fort, behandler spillet bare den første og spesielle trekk vil ikke fungere!
du kan fikse det med en kø. Vi kan enqueue alle innspill hendelser som de kommer inn. På denne måten spiller det ingen rolle om inndatahendelser kommer med liten tid mellom dem, de blir alle lagret og tilgjengelige for behandling. Når vi behandler trekkene, kan vi dequeue dem. Et spesielt trekk kan utarbeides slik:
Konklusjon
Stabler og køer er enkle datastrukturer som gjør at vi kan lagre og hente data i rekkefølge. I en stabel er det siste elementet vi går inn, den første som kommer ut. I en kø, det første elementet vi går inn er den første komme ut.
Vi kan legge til elementer i en stabel ved hjelp av push operasjon og hente elementer ved hjelp av pop operasjon. Med køer legger vi til elementer ved hjelp av enqueue – operasjonen og henter elementer ved hjelp avdequeue – operasjonen.
I Python kan vi implementere stabler og køer bare ved å bruke den innebygdeList datastruktur. Python har ogsådeque bibliotek som effektivt kan gi stabel og kø operasjoner i ett objekt. Til slutt har vi laget våre stabel-og køklasser for strammere kontroll over dataene våre.
det er mange virkelige verden bruk saker for stabler og køer, forstå dem tillater oss å løse mange datalagring problemer på en enkel og effektiv måte.