Cos’è uno Stack

Uno stack (pila) è una struttura dati basata sul principio LIFO (Last In, First Out): l’ultimo elemento inserito è il primo a essere rimosso.

Analogia: Una lattina di palline da tennis - puoi solo aggiungere o rimuovere dalla cima.

1
// Esempio visivo di uno stack
2
// Push: aggiungere elementi
3
// [3] ← top
4
// [2]
5
// [1]
6

7
// Pop: rimuovere dalla cima
8
// [2] ← top (dopo pop)
9
// [1]

Esempi pratici di utilizzo

1. Browser History: il pulsante “indietro” usa uno stack - ogni pagina visitata viene aggiunta allo stack, premendo “indietro” si esegue un pop
2. Call Stack: JavaScript usa uno stack per gestire le chiamate di funzioni
3. Undo/Redo: editor di testo usano stack per annullare/ripetere operazioni

Terminologia Stack

• Push: aggiungere un elemento alla cima dello stack
• Pop: rimuovere l’elemento dalla cima dello stack
• Top: riferimento all’elemento in cima allo stack
• Peek: visualizzare l’elemento in cima senza rimuoverlo

Implementazioni Stack

Array

Con un array, push e pop sono operazioni native di JavaScript:

1
// Stack con array
2
const stack = [];
3
stack.push(1);    // [1]
4
stack.push(2);    // [1, 2]
5
stack.push(3);    // [1, 2, 3]
6
stack.pop();      // ritorna 3, array diventa [1, 2]

Complessità con array:

• Push (fine): O(1) ✅
• Pop (fine): O(1) ✅
• Unshift (inizio): O(n) ❌ - richiede re-indicizzazione
• Shift (inizio): O(n) ❌ - richiede re-indicizzazione

Importante: Se usi un array per uno stack, usa sempre la fine (push/pop), mai l’inizio (unshift/shift).

Linked List

Implementiamo lo stack con una linked list modificata:

1
// Stack con linked list
2
// top → [3] → [2] → [1] → null
3
//       ↑
4
//     Primo elemento (LIFO)

Implementazione Stack

Classe Node per Stack

Il nodo è identico a quello delle linked lists:

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    // Assegna il valore passato al costruttore
5
    this.value = value;
6
    // Inizialmente il nodo non punta a nulla
7
    this.next = null;
8
  }
9
}
10

11
// Esempio di utilizzo
12
const newNode = new Node(11);
13
// Crea un oggetto: { value: 11, next: null }

Costruttore dello Stack

Il costruttore crea uno stack con il primo elemento. Usiamo top invece di head, e non abbiamo bisogno di bottom (equivalente di tail).

1
class Stack {
2
  constructor(value) {
3
    // Crea il primo nodo con il valore passato
4
    const newNode = new Node(value);
5

6
    // Top punta al primo nodo (cima dello stack)
7
    this.top = newNode;
8

9
    // Lo stack inizia con lunghezza 1
10
    this.length = 1;
11
  }
12
}
13

14
// Esempio di utilizzo
15
const myStack = new Stack(7);
16
// Crea uno stack con un nodo di valore 7
17
// top punta a questo nodo, length = 1

Differenze rispetto a Linked List:

• Usiamo top invece di head
• Non abbiamo bottom (non serve tail)
• Il resto è identico

Risultato in memoria:

1
{
2
  top: { value: 7, next: null },
3
  length: 1
4
}

Operazioni Stack

Push - Aggiungere alla cima

Aggiunge un nodo alla cima dello stack. Complessità: O(1)

Logica:

1. Crea un nuovo nodo
2. Il nuovo nodo punta al nodo attualmente in cima (newNode.next = top)
3. top viene aggiornato per puntare al nuovo nodo

Edge case: Se lo stack è vuoto, top punta semplicemente al nuovo nodo.

1
push(value) {
2
  // Crea il nuovo nodo
3
  const newNode = new Node(value);
4

5
  // Se lo stack è vuoto, top punta al nuovo nodo
6
  if (this.length === 0) {
7
    this.top = newNode;
8
  } else {
9
    // Il nuovo nodo punta al nodo attualmente in cima
10
    newNode.next = this.top;
11
    // Top viene aggiornato per puntare al nuovo nodo
12
    this.top = newNode;
13
  }
14

15
  // Incrementa la lunghezza
16
  this.length++;
17
  return this; // Ritorna l'intero stack
18
}

Nota: Push su uno stack con linked list è identico a unshift su una linked list normale.

Pop - Rimuovere dalla cima

Rimuove il nodo dalla cima dello stack e lo ritorna. Complessità: O(1)

Logica:

1. Salva il riferimento al nodo in cima (temp = top)
2. Sposta top al nodo successivo (top = top.next)
3. Rimuove il collegamento del nodo rimosso (temp.next = null)
4. Ritorna il nodo rimosso

Edge case: Se lo stack è vuoto, ritorna undefined.

1
pop() {
2
  // Se lo stack è vuoto, ritorna undefined
3
  if (this.length === 0) return undefined;
4

5
  // Salva il riferimento al nodo in cima
6
  let temp = this.top;
7
  // Sposta top al nodo successivo
8
  this.top = this.top.next;
9
  // Rimuove il collegamento del nodo rimosso
10
  temp.next = null;
11

12
  // Decrementa la lunghezza
13
  this.length--;
14

15
  // Ritorna il nodo rimosso
16
  return temp;
17
}

Nota: Pop su uno stack con linked list è identico a shift su una linked list normale.

Peek - Visualizzare la cima

Ritorna il valore della cima dello stack senza rimuoverlo. Complessità: O(1)

1
peek() {
2
  // Se lo stack è vuoto, ritorna undefined
3
  if (this.length === 0) return undefined;
4

5
  // Ritorna il valore del nodo in cima
6
  return this.top.value;
7
}

IsEmpty - Controllare se vuoto

Verifica se lo stack è vuoto. Complessità: O(1)

1
isEmpty() {
2
  // Ritorna true se la lunghezza è 0
3
  return this.length === 0;
4
}

Implementazione completa Stack

Ecco il codice completo delle classi Node e Stack:

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    this.value = value;
5
    this.next = null;
6
  }
7
}
8

9
// Classe per lo stack
10
class Stack {
11
  constructor(value) {
12
    const newNode = new Node(value);
13
    this.top = newNode;
14
    this.length = 1;
15
  }
16

17
  push(value) {
18
    const newNode = new Node(value);
19
    if (this.length === 0) {
20
      this.top = newNode;
21
    } else {
22
      newNode.next = this.top;
23
      this.top = newNode;
24
    }
25
    this.length++;
26
    return this;
27
  }
28

29
  pop() {
30
    if (this.length === 0) return undefined;
31
    let temp = this.top;
32
    this.top = this.top.next;
33
    temp.next = null;
34
    this.length--;
35
    return temp;
36
  }
37

38
  peek() {
39
    if (this.length === 0) return undefined;
40
    return this.top.value;
41
  }
42

43
  isEmpty() {
44
    return this.length === 0;
45
  }
46
}

Queues

Cos’è una Queue

Una queue (coda) è una struttura dati basata sul principio FIFO (First In, First Out): il primo elemento inserito è il primo a essere rimosso.

Analogia: Una coda di persone - la prima persona che entra in fila è la prima a essere servita.

1
// Esempio visivo di una queue
2
// Enqueue (aggiungi): ←
3
// Dequeue (rimuovi): →
4

5
// first → [1] → [2] → [3] ← last
6
//         ↑           ↑
7
//      Rimuovi     Aggiungi

Concetto FIFO

FIFO - First In, First Out: il primo elemento aggiunto è il primo a essere rimosso.

Esempi pratici di utilizzo

1. Coda di stampa: i documenti vengono stampati nell’ordine in cui sono stati inviati
2. Gestione task: i task vengono processati nell’ordine in cui sono stati aggiunti
3. BFS (Breadth-First Search): gli algoritmi di ricerca in ampiezza usano queue
4. Message Queue: sistemi di messaggistica processano messaggi in ordine FIFO

Terminologia Queue

• Enqueue: aggiungere un elemento alla fine della queue
• Dequeue: rimuovere l’elemento dall’inizio della queue
• First: riferimento al primo elemento della queue (quello che verrà rimosso per primo)
• Last: riferimento all’ultimo elemento della queue (dove vengono aggiunti nuovi elementi)

Implementazioni Queue

Array

Con un array ci sono due approcci, entrambi con un’operazione O(n):

1
// Approccio 1: Enqueue con push, Dequeue con shift
2
const queue = [];
3
queue.push(1);    // Enqueue: O(1) ✅
4
queue.push(2);
5
queue.shift();    // Dequeue: O(n) ❌ - richiede re-indicizzazione
6

7
// Approccio 2: Enqueue con unshift, Dequeue con pop
8
const queue2 = [];
9
queue2.unshift(1);  // Enqueue: O(n) ❌ - richiede re-indicizzazione
10
queue2.unshift(2);
11
queue2.pop();       // Dequeue: O(1) ✅

Problema: Con un array, non possiamo avere entrambe le operazioni O(1). Una delle due sarà sempre O(n).

Linked List

Con una linked list modificata, possiamo avere entrambe le operazioni O(1):

1
// Queue con linked list
2
// first → [1] → [2] → [3] ← last
3
//         ↑           ↑
4
//      Dequeue    Enqueue
5
//       O(1)        O(1)

Importante: Con una linked list per queue:

• Enqueue avviene dalla fine usando last (equivalente di tail)
• Dequeue avviene dall’inizio usando first (equivalente di head)

Implementazione Queue

Classe Node per Queue

Il nodo è identico a quello delle linked lists e degli stack:

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    // Assegna il valore passato al costruttore
5
    this.value = value;
6
    // Inizialmente il nodo non punta a nulla
7
    this.next = null;
8
  }
9
}
10

11
// Esempio di utilizzo
12
const newNode = new Node(4);
13
// Crea un oggetto: { value: 4, next: null }

Costruttore della Queue

Il costruttore crea una queue con il primo elemento. Usiamo first e last invece di head e tail.

1
class Queue {
2
  constructor(value) {
3
    // Crea il primo nodo con il valore passato
4
    const newNode = new Node(value);
5

6
    // First punta al primo nodo (inizio della queue)
7
    this.first = newNode;
8

9
    // Last punta allo stesso nodo di first (quando c'è un solo nodo)
10
    this.last = newNode;
11

12
    // La queue inizia con lunghezza 1
13
    this.length = 1;
14
  }
15
}
16

17
// Esempio di utilizzo
18
const myQueue = new Queue(4);
19
// Crea una queue con un nodo di valore 4
20
// first e last puntano entrambi a questo nodo
21
// length = 1

Differenze rispetto a Linked List:

• Usiamo first invece di head
• Usiamo last invece di tail
• Il resto è identico

Risultato in memoria:

1
{
2
  first: { value: 4, next: null },
3
  last: { value: 4, next: null },  // punta allo stesso oggetto di first
4
  length: 1
5
}

Operazioni Queue

Enqueue - Aggiungere alla fine

Aggiunge un nodo alla fine della queue. Complessità: O(1)

Logica:

1. Crea un nuovo nodo
2. L’ultimo nodo punta al nuovo nodo (last.next = newNode)
3. last viene aggiornato per puntare al nuovo nodo

Edge case: Se la queue è vuota, first e last puntano entrambi al nuovo nodo.

1
enqueue(value) {
2
  // Crea il nuovo nodo
3
  const newNode = new Node(value);
4

5
  // Se la queue è vuota, first e last puntano al nuovo nodo
6
  if (this.length === 0) {
7
    this.first = newNode;
8
    this.last = newNode;
9
  } else {
10
    // L'ultimo nodo punta al nuovo nodo
11
    this.last.next = newNode;
12
    // Last viene aggiornato per puntare al nuovo nodo
13
    this.last = newNode;
14
  }
15

16
  // Incrementa la lunghezza
17
  this.length++;
18
  return this; // Ritorna l'intera queue
19
}

Nota: Enqueue su una queue è identico a push su una linked list normale (aggiungere alla fine).

Dequeue - Rimuovere dall’inizio

Rimuove il primo nodo dalla queue e lo ritorna. Complessità: O(1)

Logica:

1. Salva il riferimento al primo nodo (temp = first)
2. Sposta first al nodo successivo (first = first.next)
3. Rimuove il collegamento del nodo rimosso (temp.next = null)
4. Ritorna il nodo rimosso

Edge cases:

• Queue vuota: ritorna undefined
• Un solo nodo: dopo la rimozione, last deve puntare a null

1
dequeue() {
2
  // Se la queue è vuota, ritorna undefined
3
  if (this.length === 0) return undefined;
4

5
  // Salva il riferimento al primo nodo
6
  let temp = this.first;
7

8
  // Edge case: se c'è un solo nodo
9
  if (this.length === 1) {
10
    this.first = null;
11
    this.last = null;
12
  } else {
13
    // Sposta first al nodo successivo
14
    this.first = this.first.next;
15
    // Rimuove il collegamento del nodo rimosso
16
    temp.next = null;
17
  }
18

19
  // Decrementa la lunghezza
20
  this.length--;
21

22
  // Ritorna il nodo rimosso
23
  return temp;
24
}

Nota: Dequeue su una queue è identico a shift su una linked list normale (rimuovere dall’inizio).

IsEmpty - Controllare se vuota

Verifica se la queue è vuota. Complessità: O(1)

1
isEmpty() {
2
  // Ritorna true se la lunghezza è 0
3
  return this.length === 0;
4
}

Peek - Visualizzare il primo elemento

Ritorna il valore del primo elemento senza rimuoverlo. Complessità: O(1)

1
peek() {
2
  // Se la queue è vuota, ritorna undefined
3
  if (this.length === 0) return undefined;
4

5
  // Ritorna il valore del primo nodo
6
  return this.first.value;
7
}

Implementazione completa Queue

Ecco il codice completo delle classi Node e Queue:

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    this.value = value;
5
    this.next = null;
6
  }
7
}
8

9
// Classe per la queue
10
class Queue {
11
  constructor(value) {
12
    const newNode = new Node(value);
13
    this.first = newNode;
14
    this.last = newNode;
15
    this.length = 1;
16
  }
17

18
  enqueue(value) {
19
    const newNode = new Node(value);
20
    if (this.length === 0) {
21
      this.first = newNode;
22
      this.last = newNode;
23
    } else {
24
      this.last.next = newNode;
25
      this.last = newNode;
26
    }
27
    this.length++;
28
    return this;
29
  }
30

31
  dequeue() {
32
    if (this.length === 0) return undefined;
33
    let temp = this.first;
34
    if (this.length === 1) {
35
      this.first = null;
36
      this.last = null;
37
    } else {
38
      this.first = this.first.next;
39
      temp.next = null;
40
    }
41
    this.length--;
42
    return temp;
43
  }
44

45
  peek() {
46
    if (this.length === 0) return undefined;
47
    return this.first.value;
48
  }
49

50
  isEmpty() {
51
    return this.length === 0;
52
  }
53
}

Confronto Stack vs Queue

Ora che abbiamo implementato entrambe le strutture, confrontiamole:

Tabella comparativa

Complessità con implementazioni diverse

Conclusione chiave:

• Gli stack possono essere implementati efficientemente sia con array che con linked list
• Le queue richiedono linked list per avere entrambe le operazioni O(1) con gli array una delle due sarà sempre O(n)

Quando usare Stack vs Queue

Usa uno Stack quando:

• Devi gestire operazioni LIFO (Last In, First Out)
• Hai bisogno di backtracking (tornare indietro nelle operazioni)
• Devi implementare undo/redo
• Lavori con chiamate ricorsive o call stack
• Devi fare parsing di espressioni (es. parentesi bilanciate)

Usa una Queue quando:

• Devi gestire operazioni FIFO (First In, First Out)
• Hai bisogno di processare elementi nell’ordine di arrivo
• Devi implementare BFS (Breadth-First Search)
• Lavori con task scheduling o message processing
• Vuoi gestire buffer o stream di dati

Esercizi e problemi comuni

Per praticare e approfondire stacks e queues, consulta la sezione dedicata agli esercizi e problemi comuni