UN pila è una struttura dati lineare che memorizza gli elementi in a Ultimo entrato/primo uscito (LIFO) o modalità First-In/Last-Out (FILO). Nello stack, un nuovo elemento viene aggiunto a un'estremità e un elemento viene rimosso solo da quell'estremità. Le operazioni di inserimento ed eliminazione sono spesso chiamate push e pop.

Le funzioni associate allo stack sono:

• vuoto() – Restituisce se lo stack è vuoto – Complessità temporale: O(1)
• misurare() – Restituisce la dimensione dello stack – Complessità temporale: O(1)
• in alto() / sbircia() – Restituisce un riferimento all'elemento più in alto dello stack – Complessità temporale: O(1)
• spingere(a) – Inserisce l’elemento ‘a’ in cima allo stack – Complessità temporale: O(1)
• pop() – Elimina l'elemento più in alto dello stack – Complessità temporale: O(1)

Implementazione:

Esistono vari modi in cui è possibile implementare uno stack in Python. Questo articolo tratta l'implementazione di uno stack utilizzando strutture dati e moduli della libreria Python.
Lo stack in Python può essere implementato nei seguenti modi:

• elenco
• Collezioni.deque
• coda.LifoQueue

Implementazione utilizzando l'elenco:

L'elenco delle strutture dati integrate in Python può essere utilizzato come uno stack. Invece di push(), append() viene utilizzato per aggiungere elementi in cima allo stack mentre pop() rimuove l'elemento in ordine LIFO.
Sfortunatamente, l’elenco presenta alcune carenze. Il problema più grande è che può incorrere in problemi di velocità man mano che cresce. Gli elementi nell'elenco vengono archiviati uno accanto all'altro in memoria, se lo stack diventa più grande del blocco di memoria che lo contiene attualmente, Python deve eseguire alcune allocazioni di memoria. Ciò può far sì che alcune chiamate append() richiedano molto più tempo di altre.

# 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: []>

Implementazione utilizzandocollections.deque:

Lo stack Python può essere implementato utilizzando la classe deque dal modulocollections. Deque è preferito alla lista nei casi in cui abbiamo bisogno di operazioni di accodamento e pop più veloci da entrambe le estremità del contenitore, poiché deque fornisce una complessità temporale O(1) per le operazioni di accodamento e pop rispetto a lista che fornisce O(n) complessità temporale.

Vengono utilizzati gli stessi metodi su deque visti nell'elenco, append() e 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([])>

Implementazione utilizzando il modulo coda

Il modulo Queue ha anche una coda LIFO, che è fondamentalmente uno Stack. I dati vengono inseriti nella coda utilizzando la funzione put() e get() estrae i dati dalla coda.

In questo modulo sono disponibili diverse funzioni:

• maxsize – Numero di elementi consentiti nella coda.
• vuoto() – Restituisce True se la coda è vuota, False altrimenti.
• pieno() – Restituisce True se ce ne sono maxsize elementi in coda. Se la coda è stata inizializzata con maxsize=0 (il valore predefinito), full() non restituisce mai True.
• Ottenere() – Rimuovere e restituire un elemento dalla coda. Se la coda è vuota, attendi finché un articolo non è disponibile.
• get_nowait() – Restituisce un elemento se è immediatamente disponibile, altrimenti solleva QueueEmpty.
• mettere (oggetto) – Metti un elemento in coda. Se la coda è piena, attendi che sia disponibile uno spazio libero prima di aggiungere l'articolo.
• put_nowait(oggetto) – Metti un elemento in coda senza bloccarlo. Se nessuno slot libero è immediatamente disponibile, rilancia QueueFull.
• qdimensione() – Restituisce il numero di elementi in coda.

# 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>

Implementazione utilizzando un elenco collegato singolarmente:

L'elenco collegato ha due metodi addHead(item) eremoveHead() che vengono eseguiti in tempo costante. Questi due metodi sono adatti per implementare uno stack.

• ottienidimensione() – Ottieni il numero di elementi nello stack.
• è vuoto() – Restituisce True se la pila è vuota, False altrimenti.
• sbirciare() – Restituisce l'elemento in cima allo stack. Se lo stack è vuoto, solleva un'eccezione.
• spingere(valore) – Inserisci un valore in testa allo stack.
• pop() – Rimuove e restituisce un valore in testa allo stack. Se lo stack è vuoto, solleva un'eccezione.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

# 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] # Ottieni la dimensione corrente dello stack def getSize(self): return self.size # Controlla se lo stack è vuoto def isEmpty(self): return self.size = = 0 # Prende l'elemento in cima allo stack def peek(self): # Controllo sanitario per vedere se # stiamo sbirciando in uno stack vuoto. if self.isEmpty(): return None return self.head.next.value # Inserisce un valore nello stack. def push(self, valore): nodo = Nodo(valore) nodo.next = self.head.next # Fa in modo che il nuovo nodo punti alla testa corrente self.head.next = nodo #!!! # Aggiorna head in modo che sia il nuovo nodo self.size += 1 # Rimuove un valore dallo stack e ritorna. def pop(self): if self.isEmpty(): raise Exception('Estraendo da uno stack vuoto') rimuove = self.head.next self.head.next = rimuove.next #!!! cambiato self.dimensione -= 1 return rimuovi.valore # Codice driver if __nome__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Stack: {stack}') for _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # nome della variabile cambiato print(f'Stack: { pila}')>

Produzione

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stack: 5->4->3->2->1>

Vantaggi dello stack:

• Gli stack sono semplici strutture dati con un insieme di operazioni ben definito, che li rende facili da comprendere e utilizzare.
• Gli stack sono efficienti per aggiungere e rimuovere elementi, poiché queste operazioni hanno una complessità temporale pari a O(1).
• Per invertire l'ordine degli elementi utilizziamo la struttura dati dello stack.
• Gli stack possono essere utilizzati per implementare funzioni di annullamento/ripristino nelle applicazioni.

Svantaggi dello stack:

• La limitazione delle dimensioni nello Stack è uno svantaggio e se sono pieni, non è possibile aggiungere altri elementi allo stack.
• Gli stack non forniscono un accesso rapido a elementi diversi dall'elemento superiore.
• Gli stack non supportano la ricerca efficiente, poiché devi estrarre gli elementi uno per uno finché non trovi l'elemento che stai cercando.