Stack vs Heap
Stack è un elenco ordinato in cui l'inserimento e l'eliminazione degli elementi dell'elenco possono essere eseguiti solo in un'estremità chiamata la parte superiore. Per questo motivo, lo stack è considerato una struttura dati LIFO (Last in First out). Heap è una struttura di dati speciale basata su alberi e soddisfa una proprietà speciale denominata proprietà heap. Inoltre, un heap è un albero completo, il che significa che non ci sono spazi vuoti tra le foglie dell'albero, ovvero in un albero completo ogni livello viene riempito prima di aggiungere un nuovo livello all'albero e i nodi in un dato livello vengono riempiti da da sinistra a destra.
Cos'è Stack?
Come accennato in precedenza, lo stack è una struttura di dati in cui gli elementi vengono aggiunti e rimossi da una sola estremità chiamata top. Gli stack consentono solo due operazioni fondamentali chiamate push e pop. L'operazione push aggiunge un nuovo elemento in cima allo stack. L'operazione pop rimuove un elemento dalla cima dello stack. Se lo stack è già pieno, quando viene eseguita un'operazione push, viene considerato un overflow dello stack. Se un'operazione pop viene eseguita su uno stack già vuoto, viene considerata un underflow dello stack. A causa del numero ridotto di operazioni che possono essere eseguite su uno stack, è considerata una struttura dati limitata. Inoltre, in base al modo in cui vengono definite le operazioni push e pop, è chiaro che gli elementi aggiunti per ultimi allo stack escono prima dallo stack. Pertanto lo stack è considerato come una struttura dati LIFO.
Cos'è Heap?
Come accennato in precedenza, heap è un albero completo che soddisfa la proprietà heap. La proprietà Heap afferma che, se y è un nodo figlio di x, il valore memorizzato nel nodo x dovrebbe essere maggiore o uguale al valore memorizzato nel nodo y (cioè valore(x) ≥ valore(y)). Questa proprietà implica che il nodo con il valore maggiore sia sempre posizionato alla radice. Un heap costruito utilizzando questa proprietà è chiamato max-heap. C'è un' altra variazione della proprietà heap che afferma il contrario. (cioè valore(x) ≤ valore(y)). Ciò implica che il nodo con il valore più piccolo verrebbe sempre posizionato alla radice, quindi chiamato min-heap. Esiste un'ampia gamma di operazioni eseguite sugli heap, come trovare il minimo (in min-heap) o il massimo (in max-heap), eliminare il minimo (in min-heap) o il massimo (in max-heap), aumentare (in max -heaps) o decrescente (in min-heaps), ecc.
Qual è la differenza tra Stack e Heap?
La principale differenza tra stack e heap è che mentre lo stack è una struttura di dati lineare, l'heap è una struttura di dati non lineare. Stack è un elenco ordinato che segue la proprietà LIFO, mentre l'heap è un albero completo che segue la proprietà heap. Inoltre, lo stack è una struttura di dati ristretta che supporta solo un numero limitato di operazioni come push e pop, mentre heap supporta un'ampia gamma di operazioni come trovare ed eliminare il minimo o il massimo, aumentare o diminuire la chiave e unire.
