CodeUtility
Facilitiamo la vita agli sviluppatori!
Strutture dati in C/C++

La struttura dati pila (stack) in C e C++

In questa lezione implementerai le operazioni di una pila, secondo la regola ultimo a entrare, primo a uscire, con un array fisso in C e std::stack in C++.

Introduzione

La pila (stack) permette di operare solo in cima: push mette un nuovo elemento in cima, pop toglie l'elemento in cima e peek guarda l'elemento in cima senza toglierlo. La pila segue la regola ultimo a entrare, primo a uscire (LIFO), come una pila di libri.

Punti importanti

  • Definisci le condizioni che devono essere sempre vere (invarianti) prima di scrivere le operazioni.
  • Gestisci i casi di struttura vuota, piena e di allocazione di memoria fallita.
  • Valuta insieme la complessità e la gestione della memoria di ogni operazione.

Guarda come funziona

Fai push e pop per vedere che l'ultimo elemento entrato è sempre il primo a uscire.

Esempi di codice C e C++

C
Esegui →
main.c
#include <stdio.h>

typedef struct {
    int data[8];
    int size;
} Stack;

int push(Stack *stack, int value) {
    if (stack->size == 8) return 0;
    stack->data[stack->size++] = value;
    return 1;
}

int pop(Stack *stack, int *value) {
    if (stack->size == 0) return 0;
    *value = stack->data[--stack->size];
    return 1;
}

int main(void) {
    Stack stack = {{0}, 0};
    int value;
    push(&stack, 10);
    push(&stack, 20);
    pop(&stack, &value);
    printf("%d\n", value);
}
Risultato dell'esecuzione
20
C++
Esegui →
main.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> values;
    values.push(10);
    values.push(20);
    std::cout << values.top() << '\n';
    values.pop();
}
Risultato dell'esecuzione
20

Confronto tra C e C++

La versione in C usa un array fisso di 8 elementi, quindi deve controllare se la pila è piena quando fa push (stack overflow) e se è vuota quando fa pop. In C++, std::stack gestisce la capacità tramite il contenitore sottostante e offre le stesse operazioni push, pop e top secondo la regola LIFO.

C

I dati (struct) e le operazioni sono separati, e la memoria viene allocata e liberata a mano.

C++

Classi e contenitori proteggono la coerenza dei dati e gestiscono da soli le proprie risorse.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Aggiungi test per la struttura vuota e per quando raggiunge la capacità massima.
  • Scrivi la liberazione della memoria e controlla che non ci siano perdite.
  • Confronta la complessità con il contenitore equivalente della libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide