Stack i Python: definition, implementeringer og eksempler

Hjem » Python » Stack i Python: definition, implementeringer og eksempler

Stakke i Python er et af de kernekoncepter, der bliver ved med at dukke op overalt, når man først begynder at kigge under motorhjelmen på rigtige programmer. – fra funktionskald til at fortryde funktioner i editorer og hvordan browsere håndterer din navigationshistorik. Selv hvis du primært skriver applikationskode på højt niveau, giver det dig en betydelig fordel at forstå, hvordan stakke fungerer (og hvordan man implementerer dem korrekt i Python), når du skal fejlfinde vanskelige problemer eller designe effektive algoritmer.

I denne guide vil vi gennemgå, hvad en stak er, hvad "Last In, First Out" egentlig betyder i praksis, hvilke operationer hver stak bør understøtte, og hvordan man implementerer stacks i Python ved hjælp af forskellige værktøjer som lists, collections.deque, queue.LifoQueue og enkeltvis linkede lister.Vi vil også tale om ydeevne, hukommelsesadfærd, trådsikkerhed og virkelige scenarier, hvor en stak er præcis den rigtige datastruktur at række ud efter.

Hvad er en stak i Python?

En stak er en lineær datastruktur, der følger LIFO-reglen (Last-In, First-Out): det sidste element, du skubber ind på stakken, er det første, der kommer ud igen.Konceptuelt kan man forestille sig en stak tallerkener, en bunke bøger eller en stak tøj: man kan kun tilføje eller fjerne genstande fra toppen, ikke fra midten eller bunden.

Denne LIFO-adfærd betyder, at når du indsætter (pusher) elementer, placeres hvert nyt element oven på de foregående, og når du fjerner (popper), tager du altid det senest tilføjede element.Du "springer aldrig frem" for at nå det tredje eller fjerde element uden at fjerne dem, der er over det.

I Python er en stak ikke en indbygget navngiven type i sig selv; i stedet implementerer vi stakke oven på eksisterende datastrukturer såsom lister, deques, LIFO-køer eller brugerdefinerede linkede lister.Hver mulighed har sine egne afvejninger med hensyn til ydeevne, hukommelsesforbrug og trådsikkerhed.

De to grundlæggende operationer på enhver stak er push og pop, men praktiske implementeringer afslører ofte et par flere hjælpere som peek (eller top), size og empty checks.Disse ekstra operationer gør det meget mere bekvemt at bruge stakke i virkelige applikationer.

Før du dykker ned i koden, skal du huske på en vigtig egenskab: en velimplementeret stak vil udføre push- og pop-operationer i konstant tid, angivet som O(1), uanset hvor mange elementer der er gemt.Den forudsigelige ydeevne er en af ​​hovedårsagerne til, at stakke er så udbredt i algoritmer og lavniveausystemer.

Core stak operationer og adfærd

Enhver brugbar stak i Python, uanset den underliggende implementering, drejer sig om en håndfuld almindelige operationer, der definerer dens opførsel.Det er langt vigtigere at forstå disse end at huske specifikke metodenavne i hvert bibliotek.

Den klassiske operation til at indsætte et element kaldes push: du tager en værdi og placerer den oven på den eksisterende stak.Efter et push bliver det nye element det, der returneres først af den næste pop-operation.

For at fjerne elementer bruger vi pop, som fjerner det øverste element fra stakken og returnerer det.Hvis stakken er tom, bør en robust implementering enten generere en fejl eller returnere en specifik værdi, der tydeligt signalerer fraværet af elementer.

De fleste stakimplementeringer eksponerer også en peek- eller top-operation, som giver dig mulighed for at se på det element, der aktuelt er øverst, uden at fjerne det fra stakken.Dette er især praktisk i algoritmer, der skal inspicere den næste værdi, men stadig vil gemme den der til senere.

To yderligere hjælpeoperationer, du ofte finder, er isempty (eller isEmpty) og size, som kontrollerer, om stakken har elementer, og hvor mange elementer den indeholder.I Python kan både den indbyggede len() og den boolske kontrol genbruges internt for at implementere disse hjælpere med minimal kode.

Med hensyn til tidskompleksitet garanterer en korrekt designet stak, at push, pop, peek og isEmpty alle kører i konstant tid O(1), og størrelsen kan enten være O(1) eller O(n), afhængigt af om implementeringen gemmer længden som et separat felt.Afgørende er det, at stakke ikke understøtter effektiv tilfældig adgang til vilkårlige positioner, sådan som arrays gør.

Hvornår og hvorfor man skal bruge en stak

Stakke skinner, når du har at gøre med processer, som du senere skal "spole tilbage" eller gennemgå i præcis den omvendte rækkefølge, som trinene blev taget i.Enhver situation, hvor du naturligt tænker "Jeg bliver nødt til at fortryde dette fra sidst til først", er en stærk kandidat til en stak.

En klassisk analogi fra den virkelige verden er at skille en maskine ad: man fjerner skruer og dele i en bestemt rækkefølge, og hvis man vil samle dem korrekt igen, skal man sætte dem tilbage i præcis den modsatte rækkefølge.Opbevaring af disse dele på en stak passer perfekt til den arbejdsgang.

I software er en af ​​de mest grundlæggende anvendelser af stakke funktionskaldstakken: hver gang en funktion kalder en anden funktion, overføres parametre, lokale variabler og returadresser til en stak i hukommelsen.Når en funktion returnerer, popper dens frame op, hvilket gendanner kalderens tilstand.

Fortryd- og fortryd-mekanismer i teksteditorer, tegneværktøjer, IDE'er og mange andre applikationer er typisk afhængige af stakke af handlinger eller tilstande.Hver brugerhandling overføres til en fortrydsstak; når du trykker på Ctrl+Z, fremviser applikationen den seneste handling og fortryder den.

Stakke bruges også i vid udstrækning i algoritmer såsom dybde-først søgning (DFS) i grafer, udtryksevaluering (parsing af parenteser, operatorer og operander), backtracking og til implementering af browserhistorik, hvor hver besøgt side sendes, og "Tilbage" viser den sidste.Disse scenarier drager fordel af de naturlige LIFO-disciplinstabler, der håndhæves og relaterer sig til kerneområder. programmeringslogik.

Implementering af en stak med Python-lister

Den enkleste måde at bygge en stak i Python er at bruge den indbyggede listetype, hvor man udnytter append()-metoden til at pushe og pop() til at fjerne det sidste element.Lister er dynamiske arrays under motorhjelmen og tilbyder al den grundlæggende funktionalitet, som en stak har brug for.

En minimal stak baseret på lister kan muligvis tilbyde hjælpefunktioner som create_stack, push, pop, isempty og show (eller top, size osv.), som alle internt manipulerer en almindelig Python-listeinstans.For eksempel kan create_stack blot returnere en tom liste, og isempty kan defineres som len(stack) == 0.

Et almindeligt mønster er at behandle slutningen af ​​listen som toppen af ​​stakken, så stack.append(item) udfører et push og stack.pop() udfører et popDette holder begge operationer i gennemsnitlig konstant tid, og koden forbliver meget læsbar og kort.

Hvis du foretrækker mere struktureret kode, kan du indpakke denne adfærd i en brugerdefineret Stack-klasse, der indkapsler listen og eksponerer tydelige metoder som push(), pop(), peek(), is_empty() og size().Indkapsling gør det nemmere at udvide stakken med ekstra kontroller eller logning senere.

Lister er relativt hukommelseseffektive, fordi hvert element gemmer sin værdi direkte uden overhead fra en pointer til en næste node, som man ville se i en linket liste.Derudover er mange Python-udviklere allerede meget fortrolige med listesemantik, hvilket gør denne tilgang nem at undervise i og vedligeholde.

Der er dog en vigtig advarsel: lister er bakket op af sammenhængende hukommelse, så når de vokser ud over den reserverede plads, skal Python allokere en ny, større blok og kopiere elementerne over.For det meste er denne omfordeling amortiseret og usynlig, men lejlighedsvis kan en enkelt append() være mærkbart langsommere end andre.

En anden ulempe er, at Python-lister ikke er trådsikre for samtidige ændringer fra flere tråde, hvilket kan blive et problem, hvis du vil bruge en stak i flertrådede programmer.I disse situationer bør du overveje alternativer som queue.LifoQueue i stedet for almindelige lister.

Brug af collections.deque som en stak

Pythons samlingsmodul tilbyder en deque (dobbelt-endet kø), som ofte er bedre egnet end lists, når du har brug for hyppige push- og pop-operationer.En deque er optimeret til hurtige appends og pops fra begge ender.

Når du bruger en deque som en stak, pusher du typisk elementer ved hjælp af append()-metoden og fjerner dem med pop(), hvor den højre ende behandles som toppen af ​​stakken.Internt implementeres deque som en dobbelt linket liste af blokke, hvilket undgår de store omfordelinger, som lister lejlighedsvis har brug for.

Det er ligetil at oprette en stak ved hjælp af deque: kald deque() for at få en tom container, og definer derefter operationer som push(stack, item), der kalder stack.append(item), og pop(stack), der kontrollerer, om stakken ikke er tom, og derefter kalder stack.pop().Yderligere hjælpere som show(stack) kan blot udskrive det aktuelle indhold.

Fordi deque er specifikt indstillet til effektiv indsættelse og sletning i begge ender, opretholder push- og pop-operationer ensartet O(1)-ydeevne, selv når strukturen vokser.Dette kan gøre deques at foretrække frem for lister til store eller meget brugte stakke.

I single-threaded kode er deque normalt et af de bedste standardvalg til implementering af stacks i Python, da det kombinerer god ydeevne, en ren API og ingen overraskelser med hensyn til kapacitetsgrænser.Den opfører sig også mere forudsigeligt med hensyn til timing, når stakken vokser sig meget stor.

Implementering af stakke med queue.LifoQueue

Når trådsikkerhed bliver vigtig, er kømodulets LifoQueue-klasse den foretrukne løsning til implementering af en stak i Python.En LifoQueue er i bund og grund en trådsikker stak med indbyggede låsemekanismer.

For at oprette en ny LifoQueue-baseret stak, instantierer du LifoQueue med en valgfri maxsize-parameter, som repræsenterer det maksimale antal elementer, som stakken kan indeholde.Internt vil køen håndtere ventetid, blokering og signalering på tværs af tråde, hvis stakken er fuld eller tom.

At skubbe et element over på en LifoQueue-stak gøres med put(item), som kan blokere, hvis stakken allerede er på sin maksimale kapacitet.Popping af elementer bruger get(), som også kan blokere, hvis stakken er tom, indtil et nyt element er tilgængeligt.

Yderligere hjælpemetoder som qsize(), full() og empty() giver dig mulighed for at inspicere stakkens aktuelle tilstand på en trådsikker måde.For eksempel fortæller full() dig, om der ikke kan tilføjes flere elementer, mens empty() angiver, om der er noget at tilføje.

Den primære ulempe ved brug af LifoQueue er ydeevne: al den synkronisering, der er nødvendig for at gøre det trådsikkert, introducerer overhead, hvilket gør operationer langsommere end dem på lister eller deques.I CPU-bundne scenarier med høj ydeevne kan dette overhead have betydning, men for mange multi-threaded applikationer er sikkerhed og korrekthed langt vigtigere.

Det er værd at bemærke, at Pythons threading ikke betyder, at threads automatisk kører på forskellige CPU-kerner på grund af Global Interpreter Lock (GIL), men LifoQueue beskytter stadig din delte stak mod race conditions og inkonsistent tilstand.For ægte parallelisme på tværs af kerner ville du have brug for multiprocessering eller andre tilgange, men konceptet med trådsikre stakke er stadig relevant for I/O-bundne eller kooperative arbejdsbelastninger.

Stakimplementering ved hjælp af en enkeltstående linket liste

En mere "klassisk" datalogi-metode til at bygge en stak i Python er at bruge en enkeltstående linket liste, hvor hver node gemmer en værdi og en pointer (reference) til den næste node.Denne tilgang giver dig en stak af dynamisk størrelse, der ikke er afhængig af sammenhængende hukommelse.

Du definerer typisk en Node-klasse med attributter for værdien og den næste reference, og implementerer derefter en Stack-klasse, der sporer en hovednode og en størrelsestæller.Ofte bruges en dummy head node til at forenkle kanttilfælde, når stakken er tom.

I dette design er toppen af ​​stakken repræsenteret af noden umiddelbart efter hovedetFor at pushe en værdi opretter du en ny node, sætter dens næste reference til den aktuelle head.next og opdaterer derefter head.next til at pege på den nye node, hvorved størrelsen øges undervejs.

At poppe et element indebærer at kontrollere, om stakken er tom, derefter tage den node, som head.next peger på, flytte head.next til den følgende node, formindske størrelsen og returnere den fjernede værdi.Denne operation har konstant tidskompleksitet, fordi kun et par pointeropdateringer er nødvendige.

Yderligere metoder som getSize(), isEmpty() og peek() er nemme at implementere med denne struktur: size spores som et heltal, isEmpty kan kontrollere, om size er nul, og peek returnerer head.next.value, hvis stakken ikke er tom.Du kan også definere en __str__-metode til at generere en læsbar streng med alle stakelementer.

Fordelene ved en linked-list-baseret stak inkluderer dynamisk vækst uden reallokering og forudsigelig O(1)-ydeevne for push og pop, selv når strukturen bliver stor.Hukommelse allokeres node for node, hvilket kan være fordelagtigt i systemer med fragmenteret hukommelse.

Ulemperne er ekstra hukommelsesoverhead til pointere (hver node gemmer mindst én reference) og mere detaljeret, kompleks kode sammenlignet med lister eller deques.For mange hverdagsprogrammer i Python er disse omkostninger ikke fordelene værd, men teknikken er fortsat værdifuld at forstå og kan være ideel til specifikke lavniveau- eller uddannelsesmæssige scenarier.

Egenskaber, effektivitet og begrænsninger af stakke

Konceptuelt set opfører en stak sig som en bunke objekter, hvor kun toppen er tilgængelig: du interagerer altid med det senest tilføjede element først.Denne begrænsning giver stakke både deres magt og deres begrænsninger.

Når det er korrekt implementeret, er læsning af top-elementet, indsættelse af et nyt og fjernelse af top-elementet alle O(1)-operationer med konstant tidDen ensartede ydeevne er ekstremt nyttig, når du designer algoritmer, der muligvis skal pushe og poppe tusindvis eller millioner af gange.

En vigtig begrænsning er, at man ikke effektivt kan nå vilkårlige elementer midt i en stak uden at skubbe alt ovenover dem frem.Hvis du konstant har brug for tilfældig adgang, kan en anden datastruktur (f.eks. en liste brugt på en array-lignende måde) være mere passende.

Hukommelsesforbrug og allokeringsmønstre afhænger i høj grad af den valgte implementering: arrays (lister) bruger sammenhængende hukommelse og kan nogle gange være nødt til at blive omallokeret, deques administrerer hukommelsesblokke for at undgå store kopier, og linkede lister spreder noder på tværs af tilgængelige hukommelsesplaceringer.Hver tilgang afvejer overhead, lokalitet og kapacitetsadfærd forskelligt.

Fra et designperspektiv er stakke bevidst simple: kun toppen er synlig, og der er ingen idé om indeksering eller indsættelse i midten.Denne enkelhed reducerer risikoen for utilsigtet misbrug og tilskynder til kode, der eksplicit modellerer LIFO-arbejdsgange.

Overvejelser vedrørende Python-stacks og threading

Når dit Python-program er single-threaded, kan du trygt vælge mellem lister og deques til implementering af stakke baseret på ydeevne og bekvemmelighed.Begge tilbyder push- og pop-funktioner og er nemme at integrere i almindelig kode.

Når du introducerer flere tråde, der deler en stak, bliver tingene mere delikate: operationer, der virker atomare på Python-niveau, kan flettes sammen på uventede måder og ødelægge den interne tilstand.Almindelige lister og deques er ikke designet til at være fuldt trådsikre, når de bruges som delte, muterbare stakke.

Deques er relativt sikre, hvis du er ekstremt disciplineret og begrænser dig selv til kun at bruge append() og pop() fra en enkelt ende på en omhyggeligt kontrolleret måde.Men selv da kan der opstå subtile problemer og kapløbsbetingelser, hvis flere tråde læser og skriver på samme tid uden ekstern synkronisering.

For robuste multi-threaded scenarier, hvor flere tråde kan pushe og pope samtidigt, er queue.LifoQueue den anbefalede stakimplementering.Dens indbyggede låse og blokerende semantik sikrer, at samtidig adgang ikke korrumperer stakken.

Ulempen er selvfølgelig, at LifoQueue-operationer (put og get) er langsommere end raw list- eller deque-metoder på grund af den ekstra koordinering mellem tråde.Om denne overhead har betydning, afhænger af din applikations ydeevnekrav og hvor ofte stakken tilgås.

Det er også værd at huske på, at Pythons threading-model stadig kører under Global Interpreter Lock, så selv med en thread-safe stak får du ikke automatisk perfekt CPU-parallelisme til CPU-bundne opgaver.For I/O-bundne programmer eller designs, der er afhængige af samtidighed snarere end rå parallelisme, er en trådsikker stak dog en essentiel byggesten.

Valg af den rigtige Python stack implementering

Med alle disse muligheder afhænger den "bedste" stakimplementering i Python i høj grad af din kontekst: single-threaded vs. multi-threaded, ydeevnefølsomhed, hukommelsesadfærd og kodeklarhed spiller alle en rolle.Der findes ikke ét valg, der er perfekt til enhver situation.

I simple, ikke-trådede scripts eller læringsmiljøer er det ofte mere end nok at bruge en liste som en stak: append() og pop() er intuitive, hurtige til de fleste arbejdsbelastninger og kræver næsten ingen standardkode.Til uddannelsesmæssige formål gør lister det også nemt at udskrive og inspicere indholdet.

Når din stak vil blive brugt meget, potentielt med mange elementer, og du ønsker ensartet hurtig push/pop med færre overraskelser relateret til hukommelsesomallokeringer, er collections.deque typisk det mest praktiske valg.Dens API afspejler lister nøje, så migrering er typisk smertefri.

Hvis du ved fra starten, at stakken vil blive tilgået fra flere tråde, især når både pushes og pops sker samtidigt, er queue.LifoQueue den sikreste løsning.Det er måske langsommere, men det sparer dig for at implementere din egen låseprotokol og hjælper med at undgå vanskelige løbsforhold.

Den enkeltstående linkede liste-tilgang er ideel, når du vil udforske eller undervise i datastrukturers interne funktioner, eller når specifikke begrænsninger gør sammenhængende arrays eller deques mindre attraktive.Det giver dig også fuld kontrol over nodelayout og -adfærd, på bekostning af mere kode og lidt mere mentalt overhead.

Uanset hvilken implementering du vælger, forbliver den underliggende idé den samme: du modellerer en "sidst ind, først ud"-struktur, der gemmer elementer oven på hinanden og giver dig hurtig og forudsigelig adgang til det senest tilføjede element.Når du først er blevet fortrolig med denne model, bliver det meget nemmere at tænke på algoritmer og systemadfærd, hvor stakke er det naturlige match.

Ved at forstå, hvordan stakke fungerer, de operationer, de understøtter, deres almindelige Python-implementeringer og deres afvejninger af ydeevne og threading, kan du trygt vælge og implementere den version, der bedst matcher dit projekts behov, samtidig med at du skriver kode, der forbliver både effektiv og nem at ræsonnere over tid..