Liste
Stack
Uno stack (detto anche “pila”) è uno speciale tipo di struttura dati che gode di queste caratteristiche:
- è una lista di elementi;
- non ha una lunghezza predefinita;
- è possibile inserire un elemento solo in testa, operazione detta push;
- è possibile estrarre un elemento solo dalla testa, operazione detta pop;
Lo stack è una struttura dati che presenta caratteristiche differenti da un array:
- non ha un accesso diretto ai suoi elementi;
- non ha una lunghezza predefinita, ma può crescere o diminuire in modo dinamico;
- protegge i suoi elementi interni, in quanto è possibile estrarre l’ultimo elemento, o inserire un nuovo elemento.
Lo stack viene definito come una coda “LIFO” ovvero Last in First Out, ovvero l’ultimo che entra è anche il primo che esce.
Lo stack è utile per tutta una serie di problemi di gestione dati dove non è possibile sapere in anticipo quanti saranno gli elementi di una lista. Di contro questa flessibilità implica la mancanza di un accesso diretto ad ogni singolo elemento, tuttavia questo semplifica e rende più sicuro l’utilizzo dello stack.
Nel mondo reale strutture di tipo stack rappresentano bene scenari dove vengono accumulati elementi in un contenitore sicuro, senza accesso diretto, e di cui è quindi possibile controllare l’accesso. Si pensi a scenari dove è necessario memorizzare una sequenza di valori secondo un ordine predefinito, oppure quando bisogna stabilire la precedenza dei calcoli in una operazione algebrica, o memorizzare i passaggi di un percorso in un labirinto.
Stack in linguaggio C/C++
Una prima possibile soluzione in C è quella di usare un array. Ma siccome un array ha una una dimensione fissa, dobbiamo gestire quella situazione in cui continuando ad aggiungere un nuovo elemento, si superano i limiti dell’array. Per farlo dobbiamo quindi creare un nuovo array, copiarci dentro i valori del vecchio array, e poi cancellarlo.
Dobbiamo poi chiaramente gestire con le variabili count e len rispettivamente il numero di elementi presenti e la lunghezza attuale dell’array (che deve essere sempre maggiore dei valori effettivamente contenuti).
Vediamo il codice:
#include <iostream>
using namespace std;
int push(char value, char data[], int count, int len) {
if (count >= len) {
len += 10;
char* newData = new char[len];
for (int i=0; i<count; i++) {
newData[i] = data[i];
data = newData;
}
delete[] data;
}
data[count] = value;
return len;
}
char pop(char data[], int count) {
return data[count];
}
int main()
{
int len=10;
char* data = new char[len];
int count=0;
len = push('a', data, count, 10);
count++;
len = push('b', data, count, 10);
count++;
len = push('c', data, count, 10);
count++;
count--;
cout << pop(data, count);
count--;
cout << pop(data, count);
count--;
cout << pop(data, count);
return 0;
}Questa soluzione funziona, ma ha dei grossi difetti:
- occupa spazio in memoria inutilizzato;
- ogni volta che bisogna ricreare l’array, il sistema deve ricopiare tutti i valori nel nuovo array;
- per stack molto grandi occorre molta memoria per duplicare l’array.
Non è quindi una soluzione efficace. La vera soluzione passa dall’uso invece dei puntatori.
Creiamo quindi una struct che contiene il valore char da memorizzare ed un secondo attributo che contiene un puntatore al valore successivo:
struct record {
char value;
record* next;
};la struct quindi contiene sia il dato che vogliamo salvare, sia il puntatore al dato successivo.
Per creare uno stack sarà sufficiente quindi la prima volta creare un nuovo record, che chiamiamo “top”, assegnargli il valore, ed assegnare il puntatore next a NULL. Ogni volta che si vuole fare push, creiamo un nuovo valore, ma questa volta assegnamo next il puntatore a top. Se si vuole fare pop procediamo al contrario: assegnamo a top il puntatore next di top, ed eliminiamo il record.
Vediamo il codice:
record* push(record* top, char value) {
record* newTop = new record;
newTop->value = value;
newTop->next = top;
return newTop;
}
record* pop(record* top) {
record* newTop = top->next;
delete top;
return newTop;
}Vediamo come si usa:
int main()
{
record* top = NULL;
top = push(top, 'a');
top = push(top, 'b');
top = push(top, 'c');
cout << top->value;
top = pop(top);
cout << top->value;
top = pop(top);
cout << top->value;
top = pop(top);
return 0;
}Coda FIFO
La coda FIFO è una lista dove ogni elemento inserito si mette in coda. In questo caso il primo ad uscire è il primo che è entrato, e così via fino ad esaurire la coda. Un esempio nel mondo reale è la coda alla cassa del supermercato, dove l’ordine di uscita è il medesimo di quello di entrata.
Le code sono strutture dati fondamentali in numerose applicazioni, come nei sistemi operativi, nei processi di processamento dati, nella gestione di elaborazioni con priorità, nella gestione dei siti web, ecc.
Coda in linguaggio C/C++
Nello stack il punto di ingresso ed uscita è lo stesso, e quindi è sufficiente usare la stessa variabile.
Con le code invece la gestione dell’ingresso è del tutto separata dall’uscita. Vediamolo con il codice. Prima di tutto definiamo il record:
struct record {
char value;
record* next;
};
Definiamo la funzione di inserimento, enqueue:
record* enqueue(record* last, char value) {
record *newrecord = new record;
newrecord->value = value;
newrecord->next = last;
return newrecord;
}Come si può vedere:
- viene creato il nuovo record
- si collega il nuovo record all’ultimo elemento della lista (la coda)
- la funzione restituisce il puntatore al nuovo record: è la nuova coda.
Quando invece si esegue un dequeue, dobbiamo gestire 3 situazioni:
- La lista è vuota: non dobbiamo fare nulla, e restituiamo un puntatore a NULL;
- La lista ha un solo elemento: è sufficiente cancellarlo, e restituiamo un puntatore a NULL;
- la lista da 2 o più elementi: in questo caso dobbiamo trovare la testa attuale (che andrà tolta) e il secondo elemento (ovvero la futura nuova testa della coda).
Per questo occorre necessariamente scorrere tutta la lista. Dichiariamo quindi due variabili:
- c: rappresenta l’elemento corrente della lista
- n: rappresenta il prossimo elemento
Quindi ci spostiamo tramite un ciclo “avanti nella fila” fino a quando:
- c sarà il secondo elemento (la futura testa)
- n sarà il primo elemento, cioè la testa attuale da eliminare
La condizione del ciclo è quindi: n->next != NULL
Una volta che abbiamo ottenuto il primo ed il secondo elemento:
- c->next = NULL: (c diventa infatti il nuovo elemento di testa)
- delete n : va cancellato il vecchio nodo di testa
A questo punto cancelliamo next e facciamo puntare current->next a NULL, e restituiamo last invariato.
Osservare la figura sopra per vedere graficamente cosa succede con l’eliminazione.
Vediamo nel codice:
record* dequeue(record *last) {
if (last == NULL) { // caso 1
return NULL;
} else if (last->next == NULL) { // caso 2
delete last;
return NULL;
} else { // caso 3
record *c = last;
record *n = current->next;
while (n->next != NULL) {
c = c->next;
n = c->next;
}
c->next = NULL;
delete n;
return last;
}
}Scriviamo poi una funzione di stampa ed il main per verificare:
void print(record *last) {
record *current = last;
while (current != NULL) {
cout << current->value << "->";
current = current->next;
}
cout << endl;
}
int main()
{
cout << "Aggiungo a,b,c" << endl;
record* last = enqueue(NULL, 'a');
last = enqueue(last, 'b');
last = enqueue(last, 'c');
print(last);
cout << "Rimuovo primo" << endl;
last = dequeue(last);
print(last);
cout << "Aggiungo d,e" << endl;
last = enqueue(last, 'd');
last = enqueue(last, 'e');
print(last);
cout << "Rimuovo primo" << endl;
last = dequeue(last);
print(last);
return 0;
}Lista concatenata
Le liste concatenate sono liste generiche di lunghezza variabile. Esse offrono caratteristiche simili alle code FIFO, solo che offrono la possibilità di accedere ad ogni singolo elemento, e di rimuovere ed inserire elementi in qualsiasi posizione. Non sono però liste veloci, per accedere ad un elemento bisogna scorrere tutta la lista per trovare l’elemento che ci interessa.
Prima di tutto definiamo una struct node, che rappresenta il singolo elemento della lista. Ogni elemento punta al successivo, come nelle code FIFO.
struct node
{
int data;
node *next;
};Vediamo ora la funzione get, che permette di ottenere l’i-esimo elemento. Anche qui scorriamo la lista usando il puntatore al successivo elemento finché non raggiungiamo la posizione desiderata:
node* get(node *last, int position) {
node* current = last;
while (position > 0) {
current = current->next;
position--;
}
return current;
}
A questo punto definiamo una funzione di aggiunta. Con questa funzione possiamo inserire un elemento in qualsiasi posizione. La funzione gestisce due casistiche:
– aggiunta in posizione 0: l’elemento viene aggiunto e diventa il nuovo elemento di coda della lista (è come la enqueue della coda);
– aggiunta in posizione diversa da 0: l’elemento viene inserito dopo l’elemento precedente, e viene collegato all’elemento successivo.
Per capire cosa viene fatto vedere la figura:
node* insert(node* last, int position, int value) {
node* new_node = new node;
new_node->data = value;
if (position==0) {
new_node->next = last;
return new_node;
}
node* current = get(last, position-1);
new_node->next = current->next;
current->next = new_node;
return last;
}Per esempio se vogliamo il terzo elemento della lista scriveremo:
node *third = get(first, 3);In pratica get è una funzione che avanza nella lista fino al nodo desiderato.
Se vogliamo eliminare un nodo introduciamo la funzione remove che elimina il nodo ad una certa posizione:
node* remove(node *last, int position) {
if (last == NULL) {
return NULL;
}
if (position == 0) {
node *current = last->next;
delete last;
return current;
}
node* previous = get(last, position-1);
node* current = previous->next;
node* next = current->next;
previous->next = next;
delete current;
return last;
}Sono possibili tre casi:
- nessun elemento in lista: viene restituito NULL
- si richiede di rimuovere il primo elemento (la coda): si recupera il puntatore al successivo, si elimina il primo elemento della lista, e si restituisce il successivo come primo elemento;
- caso generale: si ottiene l’elemento precedente, lo si “scollega” dalla lista (unendo il precedente al successivo dell’elemento da eliminare) e poi lo si cancella.
Vediamo questo ultimo caso in figura:
Vediamo un esempio di programma completo con quanto visto finora.
#include <iostream>
#include <string.h>
#include <cstdlib>
using namespace std;
struct node
{
int data;
struct node *next;
};
node* get(node *last, int position) {
node* current = last;
while (position > 0) {
current = current->next;
position--;
}
return current;
}
node* insert(node* last, int position, int value) {
node* new_node = new node;
new_node->data = value;
if (position==0) {
new_node->next = last;
return new_node;
}
node* current = get(last, position-1);
new_node->next = current->next;
current->next = new_node;
return last;
}
node* remove(node *last, int position) {
if (last == NULL) {
return NULL;
}
if (position == 0) {
node *current = last->next;
delete last;
return current;
}
node* previous = get(last, position-1);
node* current = previous->next;
if (current->next != NULL) {
node* next = current->next;
previous->next = next;
}
delete current;
return last;
}
void print(node *last) {
cout << endl << "Ecco la lista dei nodi: " << endl;
node* current = last;
int position = 0;
while (current != NULL) {
cout << position << " - Valore:" << current->data << endl;
current = current->next;
position++;
}
}
int main() {
node *first = NULL;
int action;
int count=0;
do {
cout << "1: rimuovi nodo" << endl;
cout << "2: aggiungi nodo" << endl;
cout << "3: stampa nodi" << endl;
cout << "0: esci" << endl;
cout << "Scelta: ";
cin >> action;
if (action==1) {
int position;
do {
cout << "Inserisci posizione:";
cin >> position;
} while (position < 0 || position>=count);
first = remove(first, position);
print(first);
count--;
}
if (action == 2) {
int position;
do {
cout << "Inserisci posizione:";
cin >> position;
} while (position < 0 || position>count);
cout << "Inserisci valore: ";
int value;
cin >> value;
first = insert(first, position, value);
print(first);
count++;
}
if (action == 3) {
print(first);
}
} while (action != 0);
return 0;
}