Vodnik po nizih v Pythonu

Predstavitev

Medtem ko so nekatere podatkovne strukture vsestranske in jih je mogoče uporabiti v številnih aplikacijah, so druge specializirane in zasnovane za reševanje specifičnih težav. Ena taka specializirana struktura, znana po svoji preprostosti, a izjemni uporabnosti, je sveženj.

Torej, kaj je sklad? V svojem jedru je sklad linearna podatkovna struktura, ki sledi LIFO (Last In First Out) načelo. Zamislite si to kot kup krožnikov v kavarni; vzamete samo krožnik, ki je na vrhu, in ko postavite nov krožnik, gre na vrh kupa.

Zadnji dodan element je prvi element, ki bo odstranjen

Toda zakaj je razumevanje sklada ključnega pomena? Z leti so skladi našli svoje aplikacije na številnih področjih, od upravljanja pomnilnika v vaših najljubših programskih jezikih do funkcije gumba za nazaj v vašem spletnem brskalniku. Zaradi te intrinzične preprostosti v kombinaciji z njegovo široko uporabnostjo je sklad nepogrešljivo orodje v arzenalu razvijalcev.

V tem priročniku se bomo poglobili v koncepte, ki stojijo za skladi, njihovo implementacijo, primere uporabe in še veliko več. Opredelili bomo, kaj so skladi, kako delujejo, nato pa si bomo ogledali dva najpogostejša načina implementacije podatkovne strukture skladov v Python.

Temeljni koncepti podatkovne strukture sklada

V svojem bistvu je sklad varljivo preprost, vendar ima nianse, ki mu omogočajo vsestransko uporabo v računalniški domeni. Preden se poglobimo v njegove izvedbe in praktično uporabo, si zagotovimo popolno razumevanje temeljnih konceptov, ki obdajajo nize.

Načelo LIFO (Last In First Out).

LIFO je vodilno načelo sklada. To pomeni, da zadnji element, ki vstopi v sklad, prvi zapusti. Ta značilnost razlikuje sklade od drugih linearnih podatkovnih struktur, kot so čakalne vrste.

Osnovne operacije

Vsako podatkovno strukturo definirajo operacije, ki jih podpira. Za sklade so te operacije enostavne, a bistvenega pomena:

• Push – Doda element na vrh sklada. Če je sklad poln, lahko ta operacija povzroči prelivanje sklada.

• Pop – Odstrani in vrne najvišji element sklada. Če je sklad prazen, lahko poskus izpiranja povzroči prenizek sklad.

• Peek (ali Top) – Opazuje najvišji element, ne da bi ga odstranil. Ta operacija je uporabna, če želite pregledati trenutni zgornji element, ne da bi spremenili stanje sklada.

Do sedaj bi moral biti pomen podatkovne strukture sklada in njenih temeljnih konceptov očiten. Ko gremo naprej, se bomo poglobili v njegove izvedbe in osvetlili, kako se ta temeljna načela prevedejo v praktično kodo.

Kako implementirati sklad iz nič v Python

Ko smo dojeli temeljna načela za nizi, je čas, da zavihamo rokave in se poglobimo v praktično plat stvari. Čeprav je implementacija sklada enostavna, je mogoče pristopiti na več načinov. V tem razdelku bomo raziskali dve glavni metodi implementacije sklada – z uporabo nizov in povezanih seznamov.

Implementacija sklada z uporabo nizov

Nizi, bitje sosednje pomnilniške lokacije, ponujajo intuitivno sredstvo za predstavitev skladov. Omogočajo časovno kompleksnost O(1) za dostopanje do elementov po indeksu, kar zagotavlja hitre operacije potiskanja, izpiranja in pokukanja. Poleg tega so polja lahko bolj učinkovita pri pomnilniku, ker ni dodatnih kazalcev kot pri povezanih seznamih.

Po drugi strani imajo tradicionalna polja fiksno velikost, kar pomeni, da jim po inicializaciji ni mogoče spremeniti velikosti. To lahko vodi do a preliv skladovnice če se ne spremlja. To je mogoče premagati z dinamičnimi nizi (kot je Python list), ki lahko spremeni velikost, vendar je ta operacija precej draga.

Ko vse to odpravimo, začnimo izvajati naš razred sklada z uporabo nizov v Pythonu. Najprej ustvarimo sam razred s konstruktorjem, ki vzame velikost sklada kot parameter:

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

Kot lahko vidite, smo v našem razredu shranili tri vrednosti. The size je želena velikost sklada, stack je dejansko polje, ki se uporablja za predstavitev podatkovne strukture sklada, in top je indeks zadnjega elementa v stack polje (vrh sklada).

Od zdaj naprej bomo ustvarili in razložili eno metodo za vsako od osnovnih operacij sklada. Vsaka od teh metod bo vključena v Stack razred, ki smo ga pravkar ustvarili.

Začnimo z push() metoda. Kot smo že omenili, operacija potiskanja doda element na vrh sklada. Najprej bomo preverili, ali je v skladu še kaj prostora za element, ki ga želimo dodati. Če je kupček poln, bomo dvignili Stack Overflow izjema. V nasprotnem primeru bomo le dodali element in prilagodili top in stack ustrezno:

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

Zdaj lahko definiramo metodo za odstranitev elementa z vrha sklada – the pop() metoda. Preden sploh poskusimo odstraniti element, bi morali preveriti, ali so v skladu kakršni koli elementi, ker nima smisla poskušati izstreliti element iz praznega sklada:

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

Končno lahko definiramo peek() metoda, ki samo vrne vrednost elementa, ki je trenutno na vrhu sklada:

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

In to je to! Zdaj imamo razred, ki izvaja vedenje skladov z uporabo seznamov v Pythonu.

Implementacija sklada z uporabo povezanih seznamov

Povezani seznami, pri čemer dinamične podatkovne strukture, se lahko zlahka povečajo in skrčijo, kar je lahko koristno za izvajanje skladov. Ker povezani seznami po potrebi dodelijo pomnilnik, se lahko sklad dinamično poveča in zmanjša brez potrebe po izrecnem spreminjanju velikosti. Druga prednost uporabe povezanih seznamov za izvajanje skladov je, da operacije potiskanja in izpiranja zahtevajo le preproste spremembe kazalca. Slaba stran tega je, da ima vsak element na povezanem seznamu dodaten kazalec, ki porabi več pomnilnika v primerjavi z nizi.

Kot smo že razpravljali v "Python povezani seznami" člena, je prva stvar, ki bi jo morali implementirati pred dejanskim povezanim seznamom, razred za posamezno vozlišče:

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

Ta izvedba shrani samo dve točki podatkov – vrednost, shranjeno v vozlišču (data) in sklic na naslednje vozlišče (next).

Zdaj lahko skočimo na sam dejanski razred sklada. Konstruktor bo malo drugačen od prejšnjega. Vsebovala bo samo eno spremenljivko – sklic na vozlišče na vrhu sklada:

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

Kot je bilo pričakovano, bo push() metoda doda nov element (v tem primeru vozlišče) na vrh sklada:

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

O pop() metoda preveri, ali so v skladu kakšni elementi, in odstrani najvišjega, če sklad ni prazen:

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

Na koncu peek() metoda preprosto prebere vrednost elementa z vrha sklada (če obstaja):

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

Izbira med nizi in povezanimi seznami je odvisna od posebnih zahtev in omejitev aplikacije.

Kako implementirati sklad z uporabo Pythonovih vgrajenih struktur

Za mnoge razvijalce izgradnja sklada iz nič, čeprav izobraževalna, morda ni najbolj učinkovit način za uporabo sklada v aplikacijah v resničnem svetu. Na srečo so številni priljubljeni programski jeziki opremljeni z vgrajenimi podatkovnimi strukturami in razredi, ki naravno podpirajo operacije skladov. V tem razdelku bomo raziskali ponudbe Pythona v zvezi s tem.

Python, ki je vsestranski in dinamičen jezik, nima namenskega razreda sklada. Vendar pa njegove vgrajene podatkovne strukture, zlasti seznami in razred deque iz collections modul, lahko brez težav služijo kot skladi.

Uporaba seznamov Python kot nizov

Seznami Python lahko precej učinkovito posnemajo sklad zaradi njihove dinamične narave in prisotnosti metod, kot je append() in pop().

• Potisna operacija – Dodajanje elementa na vrh sklada je tako preprosto kot uporaba append() metoda:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Pop operacija – Odstranitev najvišjega elementa lahko dosežete z pop() metoda brez argumentov:

  top_element = stack.pop() 

• Operacija Peek Dostop do vrha brez pojava je mogoč z uporabo negativnega indeksiranja:

  top_element = stack[-1] 

Uporaba deque Razred od Zbirke Moduli

O deque (okrajšava za double-ended queue) razred je še eno vsestransko orodje za implementacije skladov. Optimiziran je za hitro dodajanje in izstopanje z obeh koncev, zaradi česar je nekoliko bolj učinkovit za operacije skladov kot seznami.

• Inicializacija:

  from collections import deque
  stack = deque()
  

• Potisna operacija – Podobno kot pri seznamih, append() uporablja se metoda:

  stack.append('A')
  stack.append('B')
  

• Pop operacija – Kot seznami, pop() metoda opravi delo:

  top_element = stack.pop() 

• Operacija Peek – Pristop je enak kot pri seznamih:

  top_element = stack[-1] 

Kdaj uporabiti katerega?

Medtem ko se lahko tako seznami kot deques uporabljajo kot skladi, če strukturo primarno uporabljate kot sklad (z dodajanjem in izstopanjem z enega konca), deque je lahko nekoliko hitrejši zaradi svoje optimizacije. Toda za večino praktičnih namenov in razen če se ukvarjamo z aplikacijami, ki so kritične za zmogljivost, bi morali Pythonovi seznami zadostovati.

Morebitne težave, povezane s skladom, in kako jih premagati

Čeprav so skladi neverjetno vsestranski in učinkoviti, tako kot katera koli druga podatkovna struktura, niso imuni na morebitne pasti. Bistveno je prepoznati te izzive pri delu s skladi in imeti pripravljene strategije za njihovo reševanje. V tem razdelku se bomo poglobili v nekaj pogostih težav, povezanih s skladom, in raziskali načine, kako jih odpraviti.

Stack Overflow

To se zgodi, ko se poskusi potisniti element na sklad, ki je dosegel največjo zmogljivost. To je zlasti težava v okoljih, kjer je velikost sklada fiksna, na primer v določenih nizkonivojskih programskih scenarijih ali rekurzivnih klicih funkcij.

Če uporabljate nize, ki temeljijo na nizih, razmislite o prehodu na dinamične nize ali izvedbe povezanih seznamov, ki sami spreminjajo velikost. Drug korak pri preprečevanju prelivanja sklada je nenehno spremljanje velikosti sklada, zlasti pred potisnimi operacijami, in zagotavljanje jasnih sporočil o napakah ali pozivov za prelivanje sklada.

Če pride do prelivanja sklada zaradi pretiranih rekurzivnih klicev, razmislite o ponavljajočih se rešitvah ali povečajte omejitev rekurzije, če okolje to dopušča.

Stack Underflow

To se zgodi, ko se element poskuša odstraniti iz praznega sklada. Da se to ne bi zgodilo, vedno preverite, ali je sklad prazen, preden izvedete operacije pop ali peek. Vrnite jasno sporočilo o napaki ali ravnajte s spodnjim tokom brez zrušitve programa.

V okoljih, kjer je to sprejemljivo, razmislite o vrnitvi posebne vrednosti, ko izstopite iz praznega sklada, da označite neveljavnost operacije.

Omejitve pomnilnika

V okoljih z omejenim pomnilnikom lahko celo dinamično spreminjanje velikosti skladov (na primer tistih, ki temeljijo na povezanih seznamih) povzroči izčrpanost pomnilnika, če postanejo preveliki. Zato bodite pozorni na skupno porabo pomnilnika aplikacije in rast sklada. Morda uvedite mehko omejitev velikosti sklada.

Pomisleki glede varnosti niti

V večnitnih okoljih lahko sočasne operacije različnih niti na skupnem skladu povzročijo nedoslednosti podatkov ali nepričakovano vedenje. Možne rešitve te težave so lahko:

• Muteksi in ključavnice – Uporabite mutekse (predmete medsebojnega izključevanja) ali ključavnice, da zagotovite, da lahko samo ena nit v določenem času izvaja operacije na skladu.
• Atomske operacije – Izkoristite atomske operacije, če jih podpira okolje, da zagotovite skladnost podatkov med operacijami potiskanja in izpiranja.
• Nitni lokalni skladi – V scenarijih, kjer vsaka nit potrebuje svoj sklad, razmislite o uporabi lokalnega pomnilnika niti, da bo vsaka nit imela svoj ločen primerek sklada.

Čeprav so skladi res zmogljivi, bosta zavedanje o njihovih morebitnih težavah in aktivno izvajanje rešitev zagotovila robustne aplikacije brez napak. Prepoznavanje teh pasti je polovica bitke – druga polovica je sprejetje najboljših praks za njihovo učinkovito reševanje.

zaključek

Skladi kljub svoji na videz preprosti naravi podpirajo številne temeljne operacije v računalniškem svetu. Od razčlenjevanja zapletenih matematičnih izrazov do upravljanja klicev funkcij je njihova uporabnost široka in bistvena. Ko smo potovali skozi podrobnosti te podatkovne strukture, je jasno, da njena moč ni le v njeni učinkovitosti, ampak tudi v vsestranskosti.

Vendar pa je, kot pri vseh orodjih, njegova učinkovitost odvisna od tega, kako se uporablja. Prepričajte se le, da temeljito razumete njegova načela, morebitne pasti in najboljše prakse, da zagotovite, da lahko izkoristite pravo moč nizov. Ne glede na to, ali implementirate eno iz nič ali uporabljate vgrajene zmogljivosti v jezikih, kot je Python, bo vaše rešitve ločila premišljena uporaba teh podatkovnih struktur.

• Distribucija vsebine in PR s pomočjo SEO. Okrepite se še danes.
• PlatoData.Network Vertical Generative Ai. Opolnomočite se. Dostopite tukaj.
• PlatoAiStream. Web3 Intelligence. Razširjeno znanje. Dostopite tukaj.
• PlatoESG. Ogljik, CleanTech, Energija, Okolje, sončna energija, Ravnanje z odpadki. Dostopite tukaj.
• PlatoHealth. Obveščanje o biotehnologiji in kliničnih preskušanjih. Dostopite tukaj.
• vir: https://stackabuse.com/guide-to-stacks-in-python/