A grămadă este o structură de date liniară care stochează articole într-un Ultimul intrat/primul ieșit (LIFO) sau modul First-In/Last-Out (FILO). În stivă, un element nou este adăugat la un capăt și un element este eliminat numai de la acel capăt. Operațiile de inserare și ștergere sunt adesea numite push și pop.

Funcțiile asociate cu stiva sunt:

• gol() – Returnează dacă stiva este goală – Complexitatea timpului: O(1)
• mărimea() – Returnează dimensiunea stivei – Complexitatea timpului: O(1)
• sus() / peek() – Returnează o referință la elementul cel mai de sus al stivei – Complexitatea timpului: O(1)
• împinge(a) – Inserează elementul „a” în partea de sus a stivei – Complexitatea timpului: O(1)
• pop() – Șterge elementul cel mai de sus al stivei – Complexitatea timpului: O(1)

Implementare:

Există diferite moduri prin care o stivă poate fi implementată în Python. Acest articol acoperă implementarea unei stive folosind structuri de date și module din biblioteca Python.
Stack în Python poate fi implementat folosind următoarele moduri:

• listă
• Colecţii.deque
• coadă.LifoQueue

Implementare folosind lista:

Lista de structuri de date încorporată din Python poate fi folosită ca stivă. În loc de push(), append() este folosit pentru a adăuga elemente în partea de sus a stivei, în timp ce pop() elimină elementul în ordinea LIFO.
Din păcate, lista are câteva neajunsuri. Cea mai mare problemă este că poate întâmpina probleme de viteză pe măsură ce crește. Elementele din listă sunt stocate unul lângă celălalt în memorie, dacă stiva crește mai mare decât blocul de memorie care îl deține în prezent, atunci Python trebuie să facă unele alocări de memorie. Acest lucru poate duce la unele apeluri append() să dureze mult mai mult decât altele.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementare folosind collections.deque:

Stiva Python poate fi implementată folosind clasa deque din modulul de colecții. Deque este preferat față de listă în cazurile în care avem nevoie de operații mai rapide de adăugare și pop de la ambele capete ale containerului, deoarece deque oferă o complexitate de timp O(1) pentru operațiunile de adăugare și pop în comparație cu lista care oferă O(n) complexitatea timpului.

Sunt folosite aceleași metode pe deque ca cele văzute în listă, append() și pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementare folosind modulul de coadă

Modulul Queue are, de asemenea, o coadă LIFO, care este practic o stivă. Datele sunt inserate în coadă folosind funcția put() și get() scoate datele din coadă.

Există diverse funcții disponibile în acest modul:

• dimensiune maximă – Numărul de articole permise în coadă.
• gol() – Returnează True dacă coada este goală, False în caz contrar.
• deplin() – Returnează True dacă există dimensiune maximă articolele din coadă. Dacă coada a fost inițializată cu maxsize=0 (implicit), atunci full() nu returnează niciodată True.
• obține() – Eliminați și returnați un articol din coadă. Dacă coada este goală, așteptați până când un articol este disponibil.
• get_nowait() – Returnați un articol dacă unul este disponibil imediat, altfel ridicați QueueEmpty.
• pune (articol) – Pune un articol în coadă. Dacă coada este plină, așteptați până când un spațiu liber este disponibil înainte de a adăuga articolul.
• put_nowait(articol) – Pune un articol în coadă fără blocare. Dacă nu este disponibil imediat niciun slot gratuit, ridicați QueueFull.
• qsize() – Returnează numărul de articole din coadă.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementare folosind o listă unică legată:

Lista legată are două metode addHead(item) și removeHead() care rulează în timp constant. Aceste două metode sunt potrivite pentru a implementa o stivă.

• getSize() – Obțineți numărul de articole din teanc.
• este gol() – Returnează True dacă stiva este goală, False în caz contrar.
• arunca o privire() – Returnează elementul de sus din stivă. Dacă stiva este goală, ridicați o excepție.
• push(valoare) – Împingeți o valoare în capul stivei.
• pop() – Eliminați și returnați o valoare din capul stivei. Dacă stiva este goală, ridicați o excepție.

Mai jos este implementarea abordării de mai sus:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Obțineți dimensiunea curentă a stivei def getSize(self): return self.size # Verificați dacă stiva este goală def isEmpty(self): return self.size = = 0 # Obțineți elementul de sus al stivei def peek(self): # Verificare sanitară pentru a vedea dacă # observăm o stivă goală. if self.isEmpty(): return None return self.head.next.value # Împinge o valoare în stivă. def push(self, value): node = Node(valoare) node.next = self.head.next # Faceți noul nod să indice capul curent self.head.next = nodul #!!! # Actualizați capul pentru a fi noul nod self.size += 1 # Eliminați o valoare din stivă și reveniți. def pop(self): if self.isEmpty(): ridică Excepție('Ieșirea dintr-o stivă goală') remove = self.head.next self.head.next = remove.next #!!! self.size schimbat -= 1 return remove.value # Cod driver if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Stivă: {stivă}') pentru _ în interval (1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # nume variabilă schimbat print(f'Stiva: { stivă}')>>> 
    Ieșire    
 Stivele sunt structuri simple de date cu un set bine definit de operațiuni, ceea ce le face ușor de înțeles și de utilizat.
Stivele sunt eficiente pentru adăugarea și eliminarea elementelor, deoarece aceste operații au o complexitate de timp de O(1).
Pentru a inversa ordinea elementelor folosim structura de date stiva.
Stivele pot fi folosite pentru a implementa funcții de anulare/refacere în aplicații.
    Dezavantajele stivei:    
Restricționarea dimensiunii în stivă este un dezavantaj și, dacă sunt pline, nu puteți adăuga mai multe elemente la stivă.
Stivele nu oferă acces rapid la alte elemente decât elementul superior.
Stivele nu acceptă căutarea eficientă, deoarece trebuie să apară elementele unul câte unul până când găsiți elementul pe care îl căutați.