Guide til stakke i Python

Genudgivet af Platon

Abonnenter: 0

Introduktion

Mens nogle datastrukturer er alsidige og kan bruges i en lang række applikationer, er andre specialiserede og designet til at håndtere specifikke problemer. En sådan specialiseret struktur, kendt for sin enkelhed og alligevel bemærkelsesværdige anvendelighed, er stable.

Så hvad er en stak? I sin kerne er en stak en lineær datastruktur, der følger LIFO (Last In First Out) princippet. Tænk på det som en stak tallerkener i et cafeteria; du tager kun den plade, der er på toppen, og når du lægger en ny plade, går den til toppen af stakken.

Det sidst tilføjede element er det første element, der skal fjernes

LIFO-princippet

Men hvorfor er forståelsen af stakken afgørende? I årenes løb har stakke fundet deres applikationer på et væld af områder, lige fra hukommelsesstyring på dine foretrukne programmeringssprog til tilbage-knappens funktionalitet i din webbrowser. Denne iboende enkelhed, kombineret med dens enorme anvendelighed, gør stakken til et uundværligt værktøj i en udviklers arsenal.

I denne guide vil vi dykke dybt ned i koncepterne bag stakke, deres implementering, use cases og meget mere. Vi vil definere, hvad stakke er, hvordan de fungerer, og derefter vil vi tage et kig på to af de mest almindelige måder at implementere stakdatastruktur i Python.

Grundlæggende koncepter for en stakdatastruktur

I sin essens er en stak vildledende enkel, men den besidder nuancer, der giver den alsidige applikationer inden for beregningsområdet. Før vi dykker ned i dens implementeringer og praktiske anvendelser, lad os sikre os en bundsolid forståelse af kernekoncepterne omkring stakke.

LIFO-princippet (Last In First Out).

LIFO er det styrende princip bag en stak. Det indebærer, at det sidste element, der kommer ind i stakken, er det første, der forlader. Denne egenskab adskiller stakke fra andre lineære datastrukturer, såsom køer.

Bemærk: Et andet nyttigt eksempel til at hjælpe dig med at pakke dit hoved omkring konceptet om, hvordan stakke fungerer, er at forestille dig, at folk kommer ind og ud af en elevator - den sidste person, der kommer ind i en elevator, er den første, der kommer ud!

Grundlæggende operationer

Hver datastruktur er defineret af de operationer, den understøtter. For stakke er disse operationer ligetil, men afgørende:

Skub ud – Tilføjer et element til toppen af stakken. Hvis stakken er fuld, kan denne handling resultere i et stak overløb.

LIFO push operation

pop – Fjerner og returnerer det øverste element i stakken. Hvis stakken er tom, kan et forsøg på et pop forårsage en stak underløb.

LIFO pop operation

Kig (eller øverst) – Observerer det øverste element uden at fjerne det. Denne handling er nyttig, når du vil inspicere det aktuelle topelement uden at ændre stakkens tilstand.

Nu burde betydningen af stakdatastrukturen og dens grundlæggende koncepter være tydelig. Efterhånden som vi bevæger os fremad, vil vi dykke ned i dens implementeringer og kaste lys over, hvordan disse grundlæggende principper omsættes til praktisk kode.

Sådan implementeres en stak fra bunden i Python

Efter at have forstået de grundlæggende principper bag stakke, er det tid til at smøge ærmerne op og dykke ned i den praktiske side af tingene. Implementering af en stak, mens det er ligetil, kan gribes an på flere måder. I dette afsnit vil vi udforske to primære metoder til at implementere en stak – ved hjælp af arrays og sammenkædede lister.

Implementering af en stak ved hjælp af arrays

Arrays, væren sammenhængende hukommelsessteder, tilbyder et intuitivt middel til at repræsentere stakke. De tillader O(1) tidskompleksitet for at få adgang til elementer efter indeks, hvilket sikrer hurtige push-, pop- og kig-operationer. Arrays kan også være mere hukommelseseffektive, fordi der ikke er nogen overhead af pointere som i linkede lister.

På den anden side har traditionelle arrays en fast størrelse, hvilket betyder, at når de først er initialiseret, kan de ikke ændres. Dette kan føre til en stakoverløb hvis ikke overvåges. Dette kan overvindes af dynamiske arrays (som Python's list), som kan ændre størrelsen, men denne operation er ret dyr.

Med alt det af vejen, lad os begynde at implementere vores stakklasse ved hjælp af arrays i Python. Lad os først og fremmest oprette en klasse selv med konstruktøren, der tager stakkens størrelse som en parameter:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Som du kan se, gemte vi tre værdier i vores klasse. Det size er den ønskede størrelse på stakken, den stack er det faktiske array, der bruges til at repræsentere stakdatastrukturen, og top er indekset for det sidste element i stack array (toppen af stakken).

Fra nu af vil vi oprette og forklare en metode for hver af de grundlæggende stakoperationer. Hver af disse metoder vil være indeholdt i Stack klasse, vi lige har oprettet.

Lad os starte med push() metode. Som tidligere diskuteret tilføjer push-operationen et element til toppen af stakken. Først og fremmest vil vi kontrollere, om stakken har plads tilbage til det element, vi vil tilføje. Hvis stakken er fuld, hæver vi Stack Overflow undtagelse. Ellers tilføjer vi bare elementet og justerer top , stack derfor:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Nu kan vi definere metoden til at fjerne et element fra toppen af stakken - pop() metode. Før vi overhovedet prøver at fjerne et element, skal vi tjekke, om der er elementer i stakken, fordi det ikke nytter noget at prøve at få et element ud af en tom stak:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Endelig kan vi definere peek() metode, der bare returnerer værdien af det element, der i øjeblikket er øverst på stakken:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

Og det er det! Vi har nu en klasse, der implementerer opførsel af stakke ved hjælp af lister i Python.

Implementering af en stak ved hjælp af linkede lister

Sammenkædede lister, være dynamiske datastrukturer, kan nemt vokse og krympe, hvilket kan være gavnligt til implementering af stakke. Da sammenkædede lister allokerer hukommelse efter behov, kan stakken dynamisk vokse og reduceres uden behov for eksplicit ændring af størrelse. En anden fordel ved at bruge linkede lister til at implementere stakke er, at push- og pop-operationer kun kræver simple markørændringer. Ulempen ved det er, at hvert element i den linkede liste har en ekstra pointer, der bruger mere hukommelse sammenlignet med arrays.

Som vi allerede har diskuteret i "Python Linked Lists" artikel, er den første ting, vi skal implementere, før den faktiske linkede liste, en klasse for en enkelt node:

class Node: def __init__(self, data): self.data = data self.next = None

Tjek vores praktiske, praktiske guide til at lære Git, med bedste praksis, brancheaccepterede standarder og inkluderet snydeark. Stop med at google Git-kommandoer og faktisk lærer det!

Denne implementering gemmer kun to datapunkter - værdien gemt i noden (data) og referencen til den næste node (next).

Vores 3-delte serie om linkede lister i Python:

Nu kan vi hoppe på selve stackklassen. Konstruktøren vil være lidt anderledes end den forrige. Den vil kun indeholde én variabel - referencen til noden øverst på stakken:

class Stack: def __init__(self): self.top = None

Som forventet push() metode tilføjer et nyt element (node i dette tilfælde) til toppen af stakken:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

pop() metoden kontrollerer, om der er nogen elementer i stakken og fjerner den øverste, hvis stakken ikke er tom:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Endelig peek() metoden læser blot værdien af elementet fra toppen af stakken (hvis der er en):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Bemærk: Begges grænseflade Stack klasser er de samme - den eneste forskel er den interne implementering af klassemetoderne. Det betyder, at du nemt kan skifte mellem forskellige implementeringer uden at bekymre dig om det interne i klasserne.

Valget mellem arrays og sammenkædede lister afhænger af applikationens specifikke krav og begrænsninger.

Sådan implementeres en stak ved hjælp af Pythons indbyggede strukturer

For mange udviklere er det måske ikke den mest effektive måde at bruge en stack på i virkelige applikationer at bygge en stak fra bunden, selv om det er uddannelsesmæssigt. Heldigvis er mange populære programmeringssprog udstyret med indbyggede datastrukturer og klasser, der naturligvis understøtter stakoperationer. I dette afsnit vil vi udforske Pythons tilbud i denne henseende.

Python, som er et alsidigt og dynamisk sprog, har ikke en dedikeret stakklasse. Men dens indbyggede datastrukturer, især lister og deque-klassen fra collections modul, kan ubesværet fungere som stakke.

Brug af Python-lister som stakke

Python-lister kan efterligne en stak ret effektivt på grund af deres dynamiske natur og tilstedeværelsen af metoder som f.eks. append() , pop().

Push Operation – At tilføje et element til toppen af stakken er lige så enkelt som at bruge append() metode:
```
stack = []
stack.append('A')
stack.append('B')
```
Pop operation – Fjernelse af det øverste element kan opnås ved hjælp af pop() metode uden argument:
```
top_element = stack.pop() 
```
Peek Operation Adgang til toppen uden at poppe kan gøres ved hjælp af negativ indeksering:
```
top_element = stack[-1] 
```

Ved brug af om hvad Klasse fra samlinger Moduler

deque (forkortelse for double-ended queue) klasse er et andet alsidigt værktøj til stakimplementeringer. Det er optimeret til hurtige tilføjelser og pops fra begge ender, hvilket gør det lidt mere effektivt til stakoperationer end lister.

Initialisering:

from collections import deque
stack = deque()

Push Operation – Svarende til lister, append() metode bruges:
```
stack.append('A')
stack.append('B')
```
Pop operation – Synes godt om lister, pop() metode gør arbejdet:
```
top_element = stack.pop() 
```
Peek Operation – Fremgangsmåden er den samme som med lister:
```
top_element = stack[-1] 
```

Hvornår skal man bruge hvilken?

Mens både lister og deques kan bruges som stakke, hvis du primært bruger strukturen som en stak (med tilføjelser og pops fra den ene ende), deque kan være lidt hurtigere på grund af dens optimering. Til de fleste praktiske formål og medmindre der er tale om præstationskritiske applikationer, burde Pythons lister dog være tilstrækkelige.

Bemærk: Dette afsnit dykker ned i Pythons indbyggede tilbud til stak-lignende adfærd. Du behøver ikke nødvendigvis at genopfinde hjulet (ved at implementere stakken fra bunden), når du har så kraftfulde værktøjer lige ved hånden.

Potentielle stak-relaterede problemer og hvordan man overvinder dem

Selvom stakke er utroligt alsidige og effektive, som enhver anden datastruktur, er de ikke immune over for potentielle faldgruber. Det er vigtigt at genkende disse udfordringer, når du arbejder med stakke, og have strategier på plads til at løse dem. I dette afsnit vil vi dykke ned i nogle almindelige stak-relaterede problemer og undersøge måder at overvinde dem på.

Stack Overflow

Dette sker, når der gøres et forsøg på at skubbe et element ind på en stak, der har nået sin maksimale kapacitet. Det er især et problem i miljøer, hvor stakstørrelsen er fast, som i visse programmeringsscenarier på lavt niveau eller rekursive funktionskald.

Hvis du bruger array-baserede stakke, kan du overveje at skifte til dynamiske arrays eller linked-list-implementeringer, som ændrer størrelsen på sig selv. Et andet trin i forebyggelsen af stak-overløb er løbende at overvåge stakkens størrelse, især før push-operationer, og give klare fejlmeddelelser eller meddelelser om stak-overløb.

Hvis stackoverløb sker på grund af for mange rekursive kald, skal du overveje iterative løsninger eller øge rekursionsgrænsen, hvis miljøet tillader det.

Stack Underflow

Dette sker, når der er et forsøg på at pop et element fra en tom stak. For at forhindre dette i at ske, skal du altid kontrollere, om stakken er tom, før du udfører pop- eller kig-handlinger. Returner en klar fejlmeddelelse eller håndter underløbet yndefuldt uden at crashe programmet.

I miljøer, hvor det er acceptabelt, kan du overveje at returnere en speciel værdi, når du springer fra en tom stak for at angive operationens ugyldighed.

Hukommelsesbegrænsninger

I miljøer med begrænset hukommelse kan selv dynamisk størrelsesændring af stakke (som dem, der er baseret på sammenkædede lister) føre til udmattelse af hukommelsen, hvis de bliver for store. Hold derfor øje med applikationens samlede hukommelsesforbrug og stakkens vækst. Indfør måske en blød kasket på stakkens størrelse.

Tråd sikkerhedsbekymringer

I miljøer med flere tråde kan samtidige operationer på en delt stak af forskellige tråde føre til datainkonsistens eller uventet adfærd. Potentielle løsninger på dette problem kan være:

Mutexes og låse – Brug mutexes (gensidige udelukkelsesobjekter) eller låse for at sikre, at kun én tråd kan udføre operationer på stakken på et givet tidspunkt.
Atomiske operationer – Udnyt atomoperationer, hvis de understøttes af miljøet, for at sikre datakonsistens under push- og pop-operationer.
Tråd-lokale stakke – I scenarier, hvor hver tråd har brug for sin stack, kan du overveje at bruge thread-local storage til at give hver tråd sin separate stack-instans.

Selvom stakke faktisk er kraftfulde, vil det at være opmærksom på deres potentielle problemer og aktiv implementering af løsninger sikre robuste og fejlfrie applikationer. At erkende disse faldgruber er halvdelen af kampen – den anden halvdel vedtager bedste praksis for at løse dem effektivt.

Konklusion

Stakke, på trods af deres tilsyneladende enkle natur, understøtter mange grundlæggende operationer i computerverdenen. Fra at analysere komplekse matematiske udtryk til at administrere funktionskald, er deres anvendelighed bred og væsentlig. Efterhånden som vi har rejst gennem denne datastrukturs ins og outs, er det klart, at dens styrke ikke kun ligger i dens effektivitet, men også i dens alsidighed.

Men som med alle værktøjer afhænger dets effektivitet af, hvordan det bruges. Bare sørg for, at du har en grundig forståelse af dens principper, potentielle faldgruber og bedste praksis for at sikre, at du kan udnytte stakkens sande kraft. Uanset om du implementerer en fra bunden eller udnytter indbyggede faciliteter på sprog som Python, er det den opmærksomme anvendelse af disse datastrukturer, der vil adskille dine løsninger.