Structurile de date joacă un rol cheie în lumea programării. Ele ne ajută să ne organizăm datele într-un mod care poate fi utilizat eficient. Stiva este una dintre cele mai simple structuri de date.
Să învățăm despre stiva și implementarea sa în Python.
Cuprins
Ce este o stivă?
O stivă este similară cu teancul de cărți, scaune etc., în viața reală. Și urmează principiul Last-in/First-out (LIFO). Este cea mai simplă structură de date. Să vedem scenariul cu un exemplu din lumea reală.
Să presupunem că avem o grămadă de cărți, după cum urmează.
Atunci când vrem a treia carte de sus, trebuie să scoatem primele două cărți de sus pentru a scoate a treia carte. Aici, cartea cea mai de sus merge ultima la teanc și vine prima din teanc. Stiva de structură de date urmează același principiu Last-in/First-out (LIFO) în programare.
Operațiuni în stivă
Există în principal două operații într-o stivă
1. push(date)
Adaugă sau împinge datele în stivă.
2. pop()
Îndepărtează sau scoate din stivă elementul cel mai de sus.
Vedeți ilustrațiile de mai jos ale operațiunilor push și pop.
Vom scrie câteva funcții de ajutor care ne ajută să obținem mai multe informații despre stivă.
Să-i vedem.
arunca o privire()
Returnează elementul cel mai de sus din stivă.
este gol()
Returnează dacă stiva este goală sau nu.
Suficiente aspecte conceptuale ale structurii de date a stivei. Să trecem la implementare fără alte prelungiri.
Presupun că aveți python instalat pe computer, dacă nu, puteți încerca și compilatorul online.
Implementarea stivei
Implementarea stivei este cea mai simplă în comparație cu alte implementări ale structurii de date. Putem implementa o stivă în mai multe moduri în Python.
Să le vedem pe toate unul câte unul.
#1. Listă
Vom implementa stiva folosind lista dintr-o clasă. Să vedem implementarea pas cu pas a stivei.
Pasul 1: Scrieți o clasă numită Stack.
class Stack: pass
Pasul 2: Trebuie să menținem datele într-o listă. Să adăugăm o listă goală în clasa Stack cu elemente de nume.
class Stack: def __init__(self): self.elements = []
Pasul 3: Pentru a împinge elementele în stivă, avem nevoie de o metodă. Să scriem o metodă push care ia datele ca argument și să le anexăm la lista de elemente.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Pasul 4: În mod similar, să scriem metoda pop care scoate elementul cel mai de sus din stivă. Putem folosi metoda pop a tipului de date listă.
class Stack: ## ... def pop(self): return self.elements.pop()
Am finalizat implementarea stivei cu operațiunile necesare. Acum, să adăugăm funcțiile de ajutor pentru a obține mai multe informații despre stivă.
Pasul 5: Putem obține elementul cel mai de sus din stivă folosind indicele negativ. Elementul de cod [-1] returnează ultimul din listă. Este cel mai de sus element al stivei în cazul nostru.
class Stack: ## ... def peek(self): return self.elements[-1]
Pasul 6: Dacă lungimea listei de elemente este 0, atunci stiva este goală. Să scriem o metodă care returnează dacă elementul este gol sau nu.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Am finalizat implementarea stivei folosind tipul de date listă.
Oh! stai ca tocmai am implementat-o. Dar, nu am văzut cum să-l folosesc. Cum să-l folosești atunci?
Hai să vedem cum să-l implementăm. Trebuie să creăm un obiect pentru ca clasa Stack să-l folosească. Nu e mare lucru. Să o facem mai întâi.
class Stack: ## ... if __name__ == '__main__': stack = Stack()
Am creat obiectul stivă și gata să-l folosim. Să urmăm pașii de mai jos pentru a testa operațiunile stivei.
- Verificați dacă stiva este goală sau nu folosind metoda is_empty. Ar trebui să returneze True.
- Împingeți numerele 1, 2, 3, 4, 5 în stivă folosind metoda push.
- Metoda is_empty ar trebui să returneze False. Verifică.
- Imprimați cel mai de sus element folosind metoda peek.
- Scoateți elementul din stivă folosind metoda pop.
- Verificați elementul peek. Ar trebui să returneze elementul 4.
- Acum, scoateți toate elementele din stivă.
- Metoda is_empty ar trebui să returneze True. Verifică.
Implementarea stivei noastre este finalizată dacă trece toți pașii de mai sus. Încercați să scrieți codul pentru pașii de mai sus.
Tu ai scris codul? Nu, nu vă faceți griji, verificați codul de mai jos.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': stack = Stack() ## checking is_empty method -> true print(stack.is_empty()) ## pushing the elements stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) ## again checking is_empty method -> false print(stack.is_empty()) ## printing the topmost element of the stack -> 5 print(stack.peek()) ## popping the topmost element -> 5 stack.pop() ## checking the topmost element using peek method -> 4 print(stack.peek()) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the is_empty method for the last time -> true print(stack.is_empty())
Ura! am finalizat implementarea stivei de la zero folosind tipul de date listă. Veți vedea rezultatul așa cum este menționat mai jos dacă rulați codul de mai sus.
True False 5 4 True
Putem folosi direct tipul de date listă ca stivă. Implementarea de mai sus a stivei vă ajută să înțelegeți implementarea stivei și în alte limbaje de programare.
De asemenea, puteți consulta aceste articole legate de listă.
Să vedem deque-ul încorporat din modulul încorporat al colecțiilor care poate acționa ca o stivă.
#2. deque din colectii
Este implementat ca o coadă dublă. Deoarece susține adăugarea și îndepărtarea elementelor de la ambele capete. Prin urmare, îl putem folosi ca stivă. Îl putem face să urmeze principiul LIFO al stivei.
Este implementat folosind alte structuri de date numite listă dublu legată. Deci performanța de inserare și ștergere a elementelor este consistentă. Accesarea elementelor din lista de legătură din mijloc a durat O(n) timp. Îl putem folosi ca stivă, deoarece nu este nevoie să accesăm elementele din mijloc din stivă.
Înainte de a implementa stiva, să vedem metodele care sunt folosite pentru a implementa stiva folosind coada.
- append(data) – folosit pentru a împinge datele în stivă
- pop() – folosit pentru a elimina elementul cel mai de sus din stivă
Nu există metode alternative pentru peek și is_empty. Putem imprima întregul teanc în locul metodei peek. Apoi, putem folosi metoda len pentru a verifica dacă stiva este goală sau nu.
Să implementăm stiva folosind deque din modulul de colecții.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Asta e. Am învățat cum să implementăm stiva folosind deque din modulul încorporat pentru colecții. Veți obține rezultatul așa cum este menționat mai jos dacă executați programul de mai sus.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Până acum, am văzut două moduri de a implementa stiva. Există alte modalități de a implementa o stivă? Da! Să vedem modul final de a implementa o stivă în acest tutorial.
#3. LifoQueue
Numele LifoQueue în sine spune că urmează principiul LIFO. Prin urmare, îl putem folosi ca stivă fără nicio îndoială. Este din coada de module încorporată. LifoQueue oferă câteva metode utile care sunt utile în implementarea stivei. Să-i vedem
- put(data) – adaugă sau împinge datele în coadă
- get() – elimină sau scoate elementul cel mai de sus din coadă
- empty() – returnează dacă stiva este goală sau nu
- qsize() – returnează lungimea cozii
Să implementăm stiva folosind LifoQueue din modulul de coadă.
from queue import LifoQueue ## creating LifoQueue object stack = LifoQueue() ## checking whether stack is empty or not -> true print(stack.empty()) ## pushing the elements stack.put(1) stack.put(2) stack.put(3) stack.put(4) stack.put(5) ## again checking whether stack is empty or not -> false print(stack.empty()) ## popping all the elements print(stack.get()) print(stack.get()) print(stack.get()) ## checking the stack size print("Size", stack.qsize()) print(stack.get()) print(stack.get()) ## checking the whether stack is empty or not for the last time -> true print(stack.empty())
Veți obține rezultatul menționat mai jos dacă executați programul de mai sus fără a-l schimba.
True False 5 4 3 Size 2 2 1 True
Aplicarea Stivei
Acum, aveți suficiente cunoștințe despre stive pentru a le aplica în probleme de programare. Să vedem o problemă și să o rezolvăm folosind o stivă.
Având o expresie, scrieți un program pentru a verifica dacă parantezele, acoladele, acoladele sunt echilibrate corect sau nu.
Să vedem câteva exemple.
Intrare: „[{}]([])”
Ieșire: echilibrată
Intrare: „{[}]([])”
Ieșire: neechilibrat
Putem folosi stiva pentru a rezolva problema de mai sus. Să vedem pașii pentru a rezolva problema.
- Creați o stivă pentru a stoca personajele.
- Dacă lungimea expresiei este impară, atunci expresia nu este echilibrată
- Repetați expresia dată.
- Dacă caracterul curent este paranteza de deschidere din ( sau { sau [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]apoi iese din stivă.
- Dacă caracterul apărut se potrivește cu paranteza de început, atunci continuați, altfel parantezele nu sunt echilibrate.
- După iterație, dacă stiva este goală, atunci ecuația este echilibrată, altfel ecuația nu este echilibrată.
Putem folosi tipul de date setat pentru verificarea potrivirii parantezelor.
## stack class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 def balance_check(expression): ## checking the length of the expression if len(expression) % 2 != 0: ## not balanced if the length is odd return False ## for checking opening_brackets = set('([{') pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) ## stack initialization stack = Stack() ## iterating through the given expression for bracket in expression: ## checking whether the current bracket is opened or not if bracket in opening_brackets: ## adding to the stack stack.push(bracket) else: ## popping out the last bracket from the stack popped_bracket = stack.pop() ## checking whether popped and current bracket pair if (popped_bracket, bracket) not in pairs: return False return stack.is_empty() if __name__ == '__main__': if balance_check('[{}]([])'): print("Balanced") else: print("Not Balanced") if balance_check('{[}]([])'): print("Balanced") else: print("Not Balanced")
Putem folosi stiva pentru a rezolva multe alte probleme. Problema de mai sus este una dintre ele. Încercați să aplicați conceptul de stivă acolo unde credeți că vi se potrivește cel mai bine.
Concluzie
Da! Ai finalizat tutorialul. Sper că ți-a plăcut tutorialul la fel de mult ca și mine în timp ce l-ai făcut. Asta e pentru tutorial.
Codare fericită 🙂 👨💻