introduktion
datastrukturer organiserar lagring i datorer så att vi effektivt kan komma åt och ändra data. Stackar och köer är några av de tidigaste datastrukturerna definierade i datavetenskap.
enkelt att lära sig och lätt att implementera, deras användningsområden är vanliga och du kommer sannolikt att hitta dig själv att integrera dem i din programvara för olika uppgifter.
det är vanligt att staplar och köer implementeras med en matris eller länkad lista. Vi kommer att förlita oss på List datastruktur för att rymma både staplar och köer.
Hur fungerar de?
Stack
stackar, som namnet antyder, följer LIFO-principen (Last-in-First-Out). Som om du staplar mynt ovanpå varandra är det sista myntet vi lägger på toppen det som är det första som tas bort från stapeln senare.
för att implementera en stack behöver vi därför två enkla operationer:
-
push– lägger till ett element till toppen av stapeln:
-
pop– tar bort elementet längst upp i stapeln:
kö
köer, som namnet antyder, följer principen first-in-first-out (FIFO). Som om man väntar i kö för biobiljetterna är den första som står i kö den första som köper en biljett och njuter 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 listor
pythons inbyggda List datastruktur levereras med metoder för att simulera både stack-och köoperationer.
låt oss överväga en stapel bokstäver:
Vi kan använda samma funktioner för att implementera en kö. Funktionenpop tar eventuellt indexet för objektet vi vill hämta som ett argument.
Så vi kan använda popmed det första indexet i listan, dvs 0, för att få köliknande beteende.
Tänk på en” kö ” av frukter:
igen, här använder viappend ochpop operationer i listan för att simulera kärnverksamheten i en kö.
stackar och köer med deque-biblioteket
Python har ettdeque (uttalat ”däck”) bibliotek som ger en sekvens med effektiva metoder för att fungera som en stapel eller en kö.
deque är en förkortning för Double Ended Queue – en generaliserad kö som kan få det första eller sista elementet som lagras:
om du vill lära dig mer omdeque bibliotek och andra typer av samlingar Python ger, kan du läsa vår introduktion till Pythons Samlingar Modulartikel.
strängare implementeringar i Python
om din kod behövde en stack och du ger ett List, finns det inget som hindrar en programmerare från att ringa insertremove eller andra listfunktioner som påverkar ordningen på din stack! Detta förstör i grunden punkten att definiera en stapel, eftersom den inte längre fungerar som den ska.
det finns tillfällen då vi vill se till att endast giltiga operationer kan utföras på våra data.
Vi kan skapa klasser som bara exponerar nödvändiga metoder för varje datastruktur.
för att göra det, låt oss skapa en ny fil som heterstack_queue.py och definiera två klasser:
programmerarna som använder vårtStack ochQueue uppmuntras nu att använda metoderna för att manipulera data istället.
exempel
Tänk 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ändare kan backa sina handlingar till början av sessionen.
en stack är en idealisk passform för detta scenario. Vi kan spela in alla åtgärder användaren tar genom att trycka den till stacken. När användaren vill ångra en åtgärd kommer de att poppa den från stacken. Vi kan snabbt simulera funktionen så här:
köer har utbredd användning i programmering också. Tänk på spel som Street Fighter eller Super Smash Brothers. Spelare i dessa spel kan utföra speciella drag 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 kampspel. I ditt spel, varje gång en knapp trycks in, avfyras en inmatningshändelse. En testare märkte att om knapparna trycks för snabbt bearbetar spelet bara den första och speciella drag fungerar inte!
Du kan fixa det med en kö. Vi kan köa alla inmatningshändelser när de kommer in. På så sätt spelar det ingen roll om inmatningshändelser kommer med lite tid mellan dem, de kommer alla att lagras och vara tillgängliga för bearbetning. När vi bearbetar rörelserna kan vi dequeue dem. Ett speciellt drag kan utarbetas så här:
slutsats
stackar och köer är enkla datastrukturer som gör att vi kan lagra och hämta data i följd. I en stapel är det sista objektet vi anger det första som kommer ut. I en kö är det första objektet vi anger det första som kommer ut.
Vi kan lägga till objekt i en stapel medpush operation och hämta objekt medpop operation. Med köer lägger vi till objekt med enqueue – funktionen och hämtar objekt med dequeue – funktionen.
i Python kan vi implementera staplar och köer bara genom att använda den inbyggda List datastruktur. Python har ocksådeque bibliotek som effektivt kan tillhandahålla stack-och köoperationer i ett objekt. Slutligen har vi gjort våra stack-och köklasser för strängare kontroll över våra data.
det finns många verkliga användningsfall för staplar och köer, genom att förstå dem kan vi lösa många datalagringsproblem på ett enkelt och effektivt sätt.