Differenza Tra Stack E Heap

2024 Autore: Mildred Bawerman | [email protected]. Ultima modifica: 2023-12-16 08:39

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 all'inizio. Per questo motivo, lo stack è considerato una struttura dati Last in First out (LIFO). Heap è una struttura dati speciale basata su alberi e soddisfa una proprietà speciale chiamata proprietà heap. Inoltre, un mucchio è un albero completo, il che significa che non ci sono spazi vuoti tra le foglie dell'albero, cioè in un albero completo ogni livello viene riempito prima di aggiungere un nuovo livello all'albero e i nodi in un determinato 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 considerata come un overflow dello stack. Se un'operazione pop viene eseguita su uno stack già vuoto, viene considerata come underflow dello stack. A causa del numero limitato di operazioni che possono essere eseguite su uno stack, viene considerato come una struttura dati limitata. Inoltre, a seconda del modo in cui vengono definite le operazioni push e pop, è chiaro che gli elementi aggiunti per ultimi allo stack escono per primi 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 deve essere maggiore o uguale al valore memorizzato nel nodo y (ovvero valore (x) ≥ valore (y)). Questa proprietà implica che il nodo con il valore maggiore sarà sempre posizionato alla radice. Un heap costruito utilizzando questa proprietà è chiamato max-heap. C'è un'altra variazione della proprietà heap che afferma il contrario di questo. (cioè valore (x) ≤ valore (y)). Ciò implica che il nodo con il valore più piccolo sarebbe 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), l'eliminazione del minimo (in min-heap) o del massimo (in max-heap),tasto crescente (in max-heap) o decrescente (in min-heap), ecc.

Qual è la differenza tra Stack e Heap?

La differenza principale tra stack e heap è che mentre stack è una struttura dati lineare, heap è una struttura 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 limitata che supporta solo un numero limitato di operazioni come push e pop, mentre l'heap supporta un'ampia gamma di operazioni come la ricerca e l'eliminazione del minimo o del massimo, l'aumento o la diminuzione della chiave e l'unione.