Reverse String

Problema: Invertire una stringa utilizzando uno stack.

Strategia - Utilizzo del LIFO:

• Itera attraverso ogni carattere della stringa e push nello stack
• Pop ogni carattere dallo stack e aggiungilo alla stringa invertita
• Il principio LIFO dello stack inverte automaticamente l’ordine

Esempio: "hello" → push h, e, l, l, o → pop o, l, l, e, h → "olleh"

Complessità: O(n) tempo, O(n) spazio

1
function reverseString(string) {
2
  // Crea una nuova istanza dello stack
3
  const stack = new Stack();
4
  // Stringa che conterrà il risultato invertito
5
  let reversedString = "";
6

7
  // Itera attraverso ogni carattere della stringa
8
  for (const c of string) {
9
    // Push ogni carattere nello stack
10
    stack.push(c);
11
  }
12

13
  // Finché lo stack non è vuoto
14
  while (!stack.isEmpty()) {
15
    // Pop caratteri dallo stack e aggiungili alla stringa invertita
16
    reversedString += stack.pop();
17
  }
18

19
  // Ritorna la stringa invertita
20
  return reversedString;
21
}

1
reverseString("hello");  // "olleh"
2
reverseString("world");  // "dlrow"

Nota: Questo problema dimostra perfettamente il principio LIFO: l’ultimo carattere inserito (push) è il primo a uscire (pop).

Balanced Parentheses

Problema: Verificare se una stringa contenente solo parentesi ( e ) è bilanciata.

Strategia - Stack per tracking delle aperture:

• Per ogni ( (apertura): push nello stack
• Per ogni ) (chiusura): pop dallo stack
  • Se lo stack è vuoto prima del pop, le parentesi non sono bilanciate
• Alla fine, se lo stack è vuoto, le parentesi sono bilanciate

Esempi:

Complessità: O(n) tempo, O(n) spazio

1
function isBalancedParentheses(parentheses) {
2
  // Crea una nuova istanza dello stack
3
  const stack = new Stack();
4

5
  // Itera attraverso ogni carattere della stringa
6
  for (const p of parentheses) {
7
    // Se il carattere è una parentesi aperta
8
    if (p === '(') {
9
      // Push nello stack
10
      stack.push(p);
11
    }
12
    // Se il carattere è una parentesi chiusa
13
    else if (p === ')') {
14
      // Verifica se lo stack è vuoto o se il pop non corrisponde
15
      if (stack.isEmpty() || stack.pop() !== '(') {
16
        // Ritorna false, le parentesi non sono bilanciate
17
        return false;
18
      }
19
    }
20
  }
21

22
  // Ritorna true se lo stack è vuoto (tutte le parentesi bilanciate)
23
  return stack.isEmpty();
24
}

1
isBalancedParentheses("(())");    // true
2
isBalancedParentheses("()()");    // true
3
isBalancedParentheses("(()");     // false
4
isBalancedParentheses("())");     // false

Nota: Questo pattern è la base per verificare bilanciamento di altri simboli (es. [], {}). Può essere esteso per gestire più tipi di parentesi contemporaneamente.

Sort Stack

Problema: Ordinare gli elementi di uno stack in ordine crescente (il più piccolo in cima) utilizzando solo un altro stack temporaneo.

Strategia - Stack ausiliario per ordinamento:

• Usa un secondo stack (additionalStack) per mantenere gli elementi ordinati
• Per ogni elemento dello stack originale:
  • Pop l’elemento (temp)
  • Confronta temp con la cima di additionalStack
  • Se la cima di additionalStack è maggiore di temp, sposta elementi da additionalStack allo stack originale finché trovi la posizione corretta per temp
  • Push temp in additionalStack
• Alla fine, sposta tutti gli elementi da additionalStack allo stack originale

Esempio:

1
Stack originale: [4, 2, 3, 1] (top → bottom)
2
↓
3
Stack ordinato: [1, 2, 3, 4] (top → bottom)

Complessità: O(n²) tempo (nel caso peggiore), O(n) spazio

1
function sortStack(stack) {
2
  // Crea uno stack ausiliario per mantenere gli elementi ordinati
3
  const additionalStack = new Stack();
4

5
  // Finché lo stack originale non è vuoto
6
  while (!stack.isEmpty()) {
7
    // Pop l'elemento corrente dallo stack originale
8
    const temp = stack.pop();
9

10
    // Finché additionalStack non è vuoto e la cima è maggiore di temp
11
    while (!additionalStack.isEmpty() && additionalStack.peek() > temp) {
12
      // Sposta l'elemento da additionalStack allo stack originale
13
      // Questo libera spazio per inserire temp nella posizione corretta
14
      stack.push(additionalStack.pop());
15
    }
16

17
    // Push temp in additionalStack nella posizione corretta
18
    additionalStack.push(temp);
19
  }
20

21
  // Sposta tutti gli elementi ordinati da additionalStack allo stack originale
22
  while (!additionalStack.isEmpty()) {
23
    stack.push(additionalStack.pop());
24
  }
25
}

1
const myStack = new Stack(3);
2
myStack.push(1);
3
myStack.push(4);
4
myStack.push(2);
5
// Stack: [2, 4, 1, 3] (top → bottom)
6

7
sortStack(myStack);
8
// Stack: [1, 2, 3, 4] (top → bottom)

Nota: Questo algoritmo non è il più efficiente per ordinare, ma dimostra come manipolare stack usando solo le operazioni push/pop. In pratica, convertirebbe in array e userebbe un algoritmo di ordinamento più efficiente.

Esercizi Queue

Queue Using Stacks - Enqueue

Problema: Implementare una queue utilizzando due stack invece di una linked list. Questa è una domanda comune nei colloqui tecnici.

Contesto: Questa implementazione non è efficiente ma è importante come esercizio concettuale per capire la differenza tra LIFO e FIFO.

Strategia - Enqueue con due stack:

1. Usa due stack: stack1 (principale) e stack2 (ausiliario)
2. Per fare enqueue di un nuovo elemento:
   • Sposta tutti gli elementi da stack1 a stack2 (inverte l’ordine)
   • Push il nuovo elemento in stack1 (va sul fondo)
   • Sposta tutti gli elementi da stack2 a stack1 (ripristina l’ordine)
3. Così facendo, il primo elemento enqueued sarà sempre in cima a stack1, pronto per essere dequeued per primo

Esempio:

1
Enqueue 1: stack1 = [1]
2
Enqueue 2: stack1 → stack2 = [1], push 2, stack2 → stack1 = [1, 2]
3
Enqueue 3: stack1 → stack2 = [1, 2], push 3, stack2 → stack1 = [1, 2, 3]
4
// Il primo elemento (1) è in cima, pronto per dequeue

Complessità: O(n) tempo per enqueue, O(1) spazio aggiuntivo

1
class MyQueue {
2
  constructor() {
3
    // Stack principale dove manteniamo la queue
4
    this.stack1 = new Stack();
5
    // Stack ausiliario per riordinare gli elementi
6
    this.stack2 = new Stack();
7
  }
8

9
  enqueue(value) {
10
    // Sposta tutti gli elementi da stack1 a stack2
11
    // Questo inverte l'ordine degli elementi
12
    while (!this.stack1.isEmpty()) {
13
      this.stack2.push(this.stack1.pop());
14
    }
15

16
    // Push il nuovo valore in stack1 (ora vuoto)
17
    // Il nuovo elemento va sul "fondo" della queue
18
    this.stack1.push(value);
19

20
    // Sposta tutti gli elementi da stack2 a stack1
21
    // Questo ripristina l'ordine originale con il nuovo elemento sul fondo
22
    while (!this.stack2.isEmpty()) {
23
      this.stack1.push(this.stack2.pop());
24
    }
25
  }
26

27
  // Metodo helper per verificare se la queue è vuota
28
  isEmpty() {
29
    return this.stack1.isEmpty();
30
  }
31
}

1
const myQueue = new MyQueue();
2
myQueue.enqueue(1);  // Queue: [1]
3
myQueue.enqueue(2);  // Queue: [1, 2]
4
myQueue.enqueue(3);  // Queue: [1, 2, 3]
5
// Il primo elemento (1) sarà il primo a essere dequeued

Nota: Questo approccio rende enqueue molto inefficiente (O(n)), ma è un ottimo esercizio per capire le differenze tra stack e queue.

Queue Using Stacks - Dequeue

Problema: Implementare l’operazione dequeue per una queue basata su due stack (continuazione dell’esercizio precedente).

Strategia - Dequeue con configurazione esistente:

• Grazie alla configurazione fatta con enqueue, il primo elemento da rimuovere è sempre in cima a stack1
• Dequeue diventa semplicemente un pop da stack1
• Se la queue è vuota, ritorna null

Complessità: O(1) tempo, O(1) spazio

1
class MyQueue {
2
  constructor() {
3
    this.stack1 = new Stack();
4
    this.stack2 = new Stack();
5
  }
6

7
  enqueue(value) {
8
    // Sposta tutti gli elementi da stack1 a stack2
9
    while (!this.stack1.isEmpty()) {
10
      this.stack2.push(this.stack1.pop());
11
    }
12

13
    // Push il nuovo valore in stack1
14
    this.stack1.push(value);
15

16
    // Sposta tutti gli elementi da stack2 a stack1
17
    while (!this.stack2.isEmpty()) {
18
      this.stack1.push(this.stack2.pop());
19
    }
20
  }
21

22
  dequeue() {
23
    // Se la queue è vuota, ritorna null
24
    if (this.isEmpty()) {
25
      return null;
26
    } else {
27
      // Altrimenti, rimuovi e ritorna il primo elemento
28
      // dalla queue facendo pop da stack1
29
      return this.stack1.pop();
30
    }
31
  }
32

33
  isEmpty() {
34
    return this.stack1.isEmpty();
35
  }
36
}

1
const myQueue = new MyQueue();
2
myQueue.enqueue(1);
3
myQueue.enqueue(2);
4
myQueue.enqueue(3);
5
// Queue: [1, 2, 3]
6

7
myQueue.dequeue();  // Ritorna 1
8
myQueue.dequeue();  // Ritorna 2
9
myQueue.dequeue();  // Ritorna 3
10
myQueue.dequeue();  // Ritorna null (queue vuota)

Nota: Dequeue è O(1) perché l’elemento da rimuovere è già in cima a stack1 grazie al lavoro fatto da enqueue. Il trade-off è che enqueue è O(n).

Implementazione completa: Queue with Stacks

Ecco l’implementazione completa della classe MyQueue:

1
// Assumiamo che abbiamo già una classe Stack implementata
2
class MyQueue {
3
  constructor() {
4
    // Stack principale dove manteniamo la queue
5
    this.stack1 = new Stack();
6
    // Stack ausiliario per riordinare gli elementi
7
    this.stack2 = new Stack();
8
  }
9

10
  // Aggiunge un elemento alla fine della queue
11
  enqueue(value) {
12
    // Sposta tutti gli elementi da stack1 a stack2
13
    while (!this.stack1.isEmpty()) {
14
      this.stack2.push(this.stack1.pop());
15
    }
16

17
    // Push il nuovo valore in stack1
18
    this.stack1.push(value);
19

20
    // Sposta tutti gli elementi da stack2 a stack1
21
    while (!this.stack2.isEmpty()) {
22
      this.stack1.push(this.stack2.pop());
23
    }
24
  }
25

26
  // Rimuove e ritorna il primo elemento della queue
27
  dequeue() {
28
    if (this.isEmpty()) {
29
      return null;
30
    } else {
31
      return this.stack1.pop();
32
    }
33
  }
34

35
  // Verifica se la queue è vuota
36
  isEmpty() {
37
    return this.stack1.isEmpty();
38
  }
39

40
  // Ritorna il primo elemento senza rimuoverlo
41
  peek() {
42
    if (this.isEmpty()) {
43
      return null;
44
    } else {
45
      return this.stack1.peek();
46
    }
47
  }
48
}

Analisi dell’efficienza: Queue con Stack

Trade-off dell’implementazione con stack:

Conclusione: L’implementazione con due stack è molto inefficiente per enqueue (O(n) invece di O(1)), ma è un ottimo esercizio per capire:

• La differenza tra LIFO (stack) e FIFO (queue)
• Come trasformare una struttura dati in un’altra
• I trade-off di performance nelle scelte implementative

In pratica: Non useresti mai due stack per implementare una queue in produzione. Usa sempre una linked list o un array circolare.

Pattern comuni

Questi problemi condividono pattern ricorrenti tra stack e queue:

Pattern Stack

1. LIFO per inversione: Reverse String

   • Il principio LIFO dello stack inverte naturalmente l’ordine degli elementi
   • Utile per qualsiasi problema di inversione

2. Stack per matching/bilanciamento: Balanced Parentheses

   • Push elementi di apertura, pop quando trovi chiusure corrispondenti
   • Verifica che lo stack sia vuoto alla fine
   • Pattern fondamentale per parsing e validazione

3. Stack ausiliario per riorganizzazione: Sort Stack

   • Usa un secondo stack per mantenere elementi in ordine
   • Sposta elementi avanti e indietro tra i due stack
   • Utile per problemi che richiedono riordinamento con memoria limitata

4. Uso di peek(): Sort Stack, Balanced Parentheses

   • Controlla la cima dello stack senza rimuovere l’elemento
   • Utile per decisioni basate sul prossimo elemento

Pattern Queue

1. Conversione LIFO → FIFO: Queue Using Stacks

   • Per ottenere FIFO da stack (LIFO), devi invertire gli elementi
   • Richiede movimento continuo tra due stack
   • Trade-off: complessità temporale vs concettuale

2. Uso di strutture ausiliarie:

   • stack2 è una struttura temporanea per riordinamento
   • Pattern comune: usa strutture extra per trasformazioni
   • Importante capire quando il trade-off vale la pena

3. Edge case management:

   • Controlla sempre se la struttura è vuota prima di operazioni
   • Ritorna valori appropriati (null o undefined) per casi limite
   • Gestisci correttamente il caso di un solo elemento