Strutture di dati: Pile e code – Designveloper

Perché pile e code?

A differenza di un array, in pile e code, non c’è un’operazione di accesso casuale (non possiamo accedere a un elemento direttamente con un ‘indice’). Di solito abbiamo meno metodi/azioni su cui possiamo eseguire come push(), pop(), peek(), enqueue(), dequeue() che trattano esclusivamente l’elemento all’inizio o alla fine della struttura dei dati.

Ma…

Domanda: Questo suona così limitante poiché possiamo accedere solo al primo o all’ultimo elemento della struttura di dati. Perché mai dovremmo voler usare qualcosa del genere? Perché non usiamo semplicemente gli array per una maggiore flessibilità?

Risposta: Le pile e le code sono di solito “strutture di dati di livello superiore” costruite sopra quelle di livello inferiore (array o linked list) per limitare le operazioni che possiamo fare su di esse. Questo è un vantaggio se vogliamo un accesso limitato.

Avere questa capacità limitata su una struttura di dati è un vantaggio perché possiamo controllare chi usa questa struttura di dati che esegue solo operazioni giuste ed efficienti. Per esempio, non dovremo chiederci se qualcuno ha inserito casualmente un elemento nel mezzo della nostra lista, incasinando alcune invarianti. Questo ci ha salvato da molti problemi. Diamo un’occhiata più da vicino.

Che cos’è una pila?

Una pila è una struttura dati lineare a una estremità che modella una pila del mondo reale avendo due operazioni primarie, cioè push e pop.

In questa immagine qui sotto, possiamo vedere che un membro dei dati viene estratto dalla cima della pila e un altro viene aggiunto ad essa. C’è un puntatore superiore che punta al blocco in cima allo stack. Questo perché gli elementi in uno stack vengono sempre rimossi e aggiunti in cima alla pila. Questo comportamento è comunemente noto come LIFO (Last In First Out).

Operazioni sullo stack

Le seguenti sono le 2 operazioni di base che possono essere eseguite su uno stack.

• Funzione Push: Aggiunge un elemento in cima allo stack
• Funzione Pop: Rimuove l’elemento superiore (e potrebbe restituirlo)

Visualizzazione delle operazioni di base dello stack

Inoltre, le seguenti funzioni aggiuntive sono fornite per uno stack al fine di controllare il suo stato.

• Funzione Peek: Restituisce l’elemento superiore dello stack senza rimuoverlo o cancellarlo
• funzione isEmpty: Controlla se lo stack è vuoto o no
• funzione isFull: Controlla se lo stack è pieno o no

Tutto opera sulla cima dello stack. Non abbiamo accesso a nient’altro che alla cima. Questo è fondamentale per capire come funziona.

Analisi della complessità

La seguente tabella di complessità presuppone che tu abbia implementato uno stack usando una lista collegata

Applicazioni stack

Quando e dove si usa uno stack? Usiamo molto lo stack nella programmazione senza nemmeno accorgercene, ecco alcuni esempi:

• Può essere usato per la valutazione delle espressioni (per esempio: un algoritmo di shunting per analizzare e valutare le espressioni matematiche).
• Può essere usato per implementare le chiamate di funzione nella programmazione della ricorsione.

• Utilizzato dai meccanismi di annullamento negli editor di testo per annullare il testo che abbiamo scritto (Cmd + Z su Mac OS e Ctrl + Z su Windows)
• Utilizzato nel Browser per navigare indietro e avanti
• Può essere usato per fare una Depth First Search (DFS) su un grafico
• Utilizzato dietro le quinte per supportare la ricorsione tenendo traccia delle precedenti chiamate di funzione

Che cosa è una coda?

Una coda è anche una struttura dati lineare che modella le code del mondo reale avendo due operazioni primarie, cioè enqueue (possiamo pensare a questo come “entrare nella coda”) e dequeue (possiamo anche pensare a questo come “cancellare dalla coda”). Questa struttura è chiamata “coda” a causa del fatto che assomiglia ad una coda del mondo reale – (dove le persone aspettano in una coda).

Ogni coda ha una parte anteriore e una posteriore (a volte chiamata “posteriore”). Noi inseriamo elementi attraverso la parte posteriore e li rimuoviamo attraverso la parte anteriore.

Una coda è una struttura FIFO (First In First Out – l’elemento posto per primo può essere raggiunto per primo) che si trova comunemente in molti linguaggi di programmazione.

Operazioni della coda

Le seguenti sono le 3 operazioni di base che possono essere eseguite su una coda.

• Funzione Enqueue: Aggiunge un elemento alla fine della coda
• Funzione Dequeue: Rimuovere l’elemento dall’inizio della coda
• Funzione Peeking: Guardare il valore all’inizio della coda senza rimuoverlo

Analisi della complessità

Come possiamo vedere nell’immagine, le operazioni di enqueuing e dequeuing richiedono un tempo costante O(1). Tuttavia, controllare se un elemento è contenuto nella coda è un tempo lineare O(n) poiché avremmo potenzialmente bisogno di scansionare tutti gli elementi.

C’è anche la rimozione degli elementi (non il dequeuing) internamente. Richiede un tempo lineare poiché dobbiamo scansionare tutti gli elementi nel caso peggiore.

Applicazioni delle code

• Utilizzate per gestire i thread nel multithreading.
• Può essere usato per tenere traccia in modo efficiente degli x elementi aggiunti più di recente
• Gestione delle richieste del web server dove vogliamo che il primo arrivato serva per primo. Per esempio: In qualsiasi momento, il nostro server web può servire solo fino a un massimo di 50 persone contemporaneamente.

Se arrivano 70 richieste in un breve periodo di tempo, non saremo in grado di processarle tutte. Quindi il webserver estrae solo 50 richieste dalla coda e mette le rimanenti 20 in attesa. Quando il webserver finisce di processare una richiesta, mette in coda la successiva da servire e continua a farlo fino a quando la coda è vuota.

• Breadth-first search (BFS) graph traversal
• Usato per implementare sistemi di accodamento (es.: code di priorità)
• Usato nella stampante di rete: La stampante può servire solo una singola richiesta alla volta. Quindi se arrivano altre richieste quando la stampante è occupata, il programma che gestisce la stampante non rifiuterà quelle richieste ma le metterà in una coda in attesa di esecuzione. La prima richiesta sarà servita per prima (FIFO).

Speriamo che questo articolo vi abbia dato un’idea di pile e code. Non dimenticate di iscrivervi al nostro blog e di seguire Designveloper su Facebook, Twitter e LinkedIn.

E questi sono altri articoli che potrebbero piacervi:

• Cos’è l’architettura delle applicazioni web?
• Strutture di dati e loro applicazioni
• Cos’è la notazione Big O?