Differenza tra struttura dati LIFO e FIFO in informatica

Pila o Stack

In informatica, lo Stack in italiano pila è un tipo di dati astratto che funge da raccolta di elementi, con due operazioni principali: PUSH, che aggiunge un elemento alla raccolta e POP che rimuove l’elemento aggiunto più di recente che non è stato ancora rimosso.

Generalmente, gli stack si basano sul principio LIFO (Last In First Out), ovvero l’elemento inserito per ultimo è il primo elemento a uscire dalla lista. La pila si chiama pila perché si comporta come una pila del mondo reale, ad esempio un mazzo di carte o una pila di piatti, oggetti ecc. Ogni volta che viene aggiunto un elemento, va in cima alla pila e l’unico elemento che può essere rimosso è l’elemento che si trova in cima alla pila.

Per utilizzare uno stack in modo efficiente, dobbiamo controllare anche lo stato dello stack. Per lo stesso scopo, la seguente funzionalità viene aggiunta agli stack:

peek () – ottiene l’elemento dati in cima allo stack, senza rimuoverlo.
isFul () – verifica che lo stack sia pieno.
isEmpty () – controlla se lo stack è vuoto.

Applicazione della pila

Parole invertite
Analisi
Conversione di espressioni (da infisso a suffisso, da suffisso a prefisso ecc.).

Differenza tra struttura dati LIFO e FIFO in informatica

Coda

Proprio come lo Stack, la Queue in italiano Coda è un tipo di dati astratto o una struttura di dati lineare in cui il primo elemento viene inserito da un’estremità denominata REAR (chiamata anche coda) e la rimozione dell’elemento esistente avviene dall’altra estremità denominata FRONT (chiamato anche testa).

In genere, le code sono strutture dati basate sul principio FIFO (First In First out), ovvero l’elemento inserito per primo è il primo elemento a uscire dalla lista. Questo è esattamente il modo in cui funziona il sistema di code nel mondo reale. Ad esempio, mentre aspetti in fila al tuo negozio di alimentari preferito, il primo in fila sarà il primo ad andarsene, con nuove persone che verranno aggiunte in fondo alla coda.

Il processo di aggiunta di un elemento alla coda viene indicato come Enqueue mentre il processo di rimozione di un elemento dalla coda viene denominato Dequeue.

Applicazioni di coda

Gestione degli interrupt nei sistemi in tempo reale. Le interruzioni vengono gestite nello stesso ordine in cui sono arrivate, ovvero chi primo arriva, primo servito.
I sistemi telefonici del Call Center utilizzano le code per trattenere le persone che li chiamano in un ordine, fino a quando un rappresentante dell’assistenza non è libero.
Servire le richieste su una singola risorsa condivisa come una stampante, la pianificazione delle attività della CPU ecc.

Differenza tra strutture dati a pila e coda

BASE DI CONFRONTO	PILA – LIFO	CODA – FIFO
Principio di funzionamento	Gli stack si basano sul principio Last In First Out (LIFO), ovvero l’elemento inserito per ultimo è il primo elemento a uscire dalla lista.	Le code sono strutture di dati basate sul principio FIFO (First In First out), ovvero l’elemento inserito al primo è il primo elemento a uscire dalla lista.
Inserimento e cancellazione	L’inserimento e la cancellazione nelle pile avviene solo da un estremo della lista riferito in alto.	L’inserimento e la cancellazione nelle code avvengono dagli estremi opposti della lista.
Puntatore di riferimento	Uno stack richiede un solo puntatore di riferimento, denominato puntatore superiore, che punta sempre all’ultimo elemento presente nell’elenco.	Una coda richiede due puntatori di riferimento denominati puntatori FRONT e REAR.
Bandiere	Negli stack viene mantenuto un solo flag per accedere alla lista che punta sempre all’ultimo elemento presente nella lista.	Nelle code vengono mantenuti due flag per accedere all’elenco.
Operazioni	Le operazioni in stack vengono chiamate PUSH e POP. L’operazione push aggiunge un’operazione nello stack mentre l’operazione POP rimuove un elemento nello stack.	In coda, le operazioni vengono denominate Enqueue e Dequeue. L’operazione di accodamento sta aggiungendo un’operazione nella coda mentre Dequeue sta rimuovendo un elemento nella coda.
Estensioni	Una pila non può essere suddivisa in sottosezioni e non ha estensioni.	Una coda può essere suddivisa in sottosezioni con le seguenti estensioni: Circle Queue, Priority queue, Double Ended Queue e Simple Queue.
Natura	Una struttura di dati dello stack non è necessariamente una raccolta ordinata di elementi di dati.	Una struttura di dati della coda è una raccolta ordinata di elementi di dati.
Inserimento di un elemento	Gli elementi più e meno accessibili sono indicati come TOP e BOTTOM della pila.	L’inserimento di un elemento viene eseguito all’estremità FRONT e la cancellazione dall’estremità REAR.
Verificare se una pila o una coda è vuota	Per verificare se uno stack è vuoto, viene utilizzata la seguente condizione: TOP == – 1 .	Per verificare se una coda è vuota, viene utilizzata la seguente condizione: FRONT == – 1 \|\| ANTERIORE == POSTERIORE + 1.
Verificare se una pila o una coda è piena	Per verificare se uno stack è pieno, viene utilizzata la seguente condizione: TOP == MAX-1.	Per verificare se una coda è piena, viene utilizzata la seguente condizione: REAR == MAX-1.
Pianificazione delle attività	La pianificazione delle attività in base al sistema operativo utilizza la coda o un interrupt di sistema è un buon esempio in cui viene utilizzato il meccanismo della coda.	La pianificazione delle attività in base alla coda utilizzata dal sistema operativo o al modo in cui funziona la chiamata di sistema ricorsiva, utilizza il meccanismo dello stack.
Applicazione	Stack viene utilizzato in infisso per la conversione di suffissi, algoritmi di pianificazione, ricerca approfondita e valutazione di un’espressione.	Una coda offre servizi di ricerca operativa, trasporti e informatica che coinvolgono persone, dati, eventi e oggetti da archiviare per una successiva elaborazione.