Stack (pila)
Ultimo aggiornamento
Uno stack, o pila, è una collezione con un solo estremo aperto. Aggiungi un valore facendo push in cima e ne togli uno facendo pop dalla stessa cima, quindi l'ultimo valore entrato è sempre il primo a uscire. È questo il significato di LIFO, ed è tutta la regola: non c'è modo di raggiungere il centro senza prima togliere ciò che sta sopra. Premi Play qui sopra e guarda la colonna crescere a ogni push e ridursi dallo stesso estremo a ogni pop.
Il vincolo è proprio il punto. Siccome entrambe le operazioni toccano solo la cima, ciascuna costa O(1) per quanto alta diventi la pila, e questa prevedibilità spiega perché gli stack stanno sotto a gran parte dell'informatica: lo stack delle chiamate che esegue la ricorsione, la cronologia degli annullamenti in un editor, il bilanciamento delle parentesi in un parser e lo stack esplicito che trasforma una ricerca in profondità ricorsiva in un ciclo. Cambia l'estremo da cui togli e ottieni invece una coda.
Complessità temporale e spaziale
Per lo stack standard basato su array o su lista concatenata:
| Operazione | Complessità | Note |
|---|---|---|
| Push | O(1) | O(1) ammortizzato su un array dinamico, che ogni tanto si ridimensiona. |
| Pop | O(1) | Sempre l'elemento in cima, quindi non serve spostare nulla. |
| Peek (cima) | O(1) | Legge la cima senza toglierla. |
| Ricerca | O(n) | Non è lo scopo di uno stack: devi scendere facendo pop uno per uno. |
| Spazio | O(n) | Una posizione per ogni valore memorizzato. |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Lo stack parte vuoto, con la cima che non punta a nulla. |
| 2 | Push scrive il valore nella posizione della cima e sposta la cima in su di uno. |
| 3 | Ogni push successivo finisce subito sopra il valore precedente. |
| 4 | Pop legge il valore in cima, poi sposta la cima in giù di uno. |
| 5 | Il valore restituito è sempre quello inserito più di recente. |
| 6 | Fare pop su uno stack vuoto è un errore, chiamato stack underflow, quindi il codice reale controlla prima is_empty(). |
Esempio svolto
Push di 3, 7, 5 e poi svuotamento dello stack:
| Operazione | Stack (dal fondo alla cima) | Restituisce |
|---|---|---|
push(3) | [3] | niente |
push(7) | [3, 7] | niente |
push(5) | [3, 7, 5] | niente |
pop() | [3, 7] | 5, il valore più recente |
pop() | [3] | 7 |
pop() | [] | 3, il valore più vecchio, per ultimo |
Quando usare uno stack
| Usalo quando | Evitalo quando |
|---|---|
| Ti serve riavere per primo l'elemento più recente: annulla, pulsante indietro, bilanciamento delle parentesi | Ti serve per primo l'elemento più vecchio, cioè una coda |
| Stai trasformando un algoritmo ricorsivo in uno iterativo | Devi cercare o accedere per indice al centro dei dati |
| Stai analizzando strutture annidate come espressioni, JSON o HTML | Molti lettori hanno bisogno di accesso arbitrario, dove un array o una mappa funzionano meglio |
Vuoi inserimento e rimozione garantiti in O(1) senza ribilanciamenti | Devi tenere i dati ordinati, cosa che ti dà un heap o un albero |
Codice Stack
Un'implementazione di Stack pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Stack in Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Codice Stack in JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Codice Stack in Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Codice Stack in C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Codice Stack in C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Domande frequenti sullo stack
Cosa significa LIFO in uno stack?
Last in, first out, cioè l'ultimo a entrare è il primo a uscire: il valore inserito più di recente è il primo a essere estratto. L'immagine classica è una pila di piatti, prendi il piatto che hai appena appoggiato, non quello in fondo. Una coda segue la disciplina opposta, FIFO.
Qual è la differenza tra pila e coda?
Solo l'estremo da cui togli. Entrambe aggiungono a un estremo in
O(1); uno stack toglie dallo stesso estremo (LIFO), una coda dall'estremo opposto (FIFO). Tutto il resto, compresa la tabella della complessità qui sopra, è identico.Quali sono le operazioni principali di uno stack?
push aggiunge un valore in cima, pop toglie e restituisce il valore in cima, peek (a volte top) legge la cima senza toglierla e is_empty indica se è rimasto qualcosa. Tutte e quattro costano O(1).Cos'è uno stack overflow?
Fare push su uno stack che non ha più spazio. Il caso famoso è lo stack delle chiamate: ogni chiamata di funzione aggiunge un frame, quindi una ricorsione che non raggiunge mai il caso base continua ad aggiungerne finché si supera il limite dello stack del runtime e il programma va in crash. L'errore speculare, fare pop su uno stack vuoto, è uno stack underflow.
Come si implementa uno stack?
In due modi comuni. Un array dinamico fa push e pop in coda, con costo
O(1) ammortizzato e buon uso della cache: così funzionano la list di Python e l'ArrayDeque di Java. Una lista concatenata fa push e pop in testa, O(1) anche nel caso peggiore e senza ridimensionamenti, ma costa un puntatore per elemento. std::stack di C++ è un adattatore che per impostazione predefinita usa std::deque, un array segmentato, e accetta un altro contenitore se glielo passi.Dove si usano gli stack nei programmi reali?
Lo stack delle chiamate per le funzioni e la ricorsione, la cronologia di annulla e ripeti, la navigazione indietro del browser, la valutazione delle espressioni e il bilanciamento delle parentesi nei parser, e lo stack esplicito che converte una ricerca in profondità ricorsiva in un ciclo iterativo.
Risorse correlate
Altre visualizzazioni
