03/29/2024

Înțelegerea implementării stivei în Python

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.

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ă.

  Cum se face o captură de ecran pe Chromebook

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.

  11 cele mai bune aplicații de fitness care te ajută să te antrenezi de oriunde

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
  8 Cel mai bun software de management al clienților pentru interacțiune și automatizare

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ă 🙂 👨‍💻