Pila e coda

Due Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti → che differiscono solo per l'ordine in cui gli elementi escono.

Pila (stack) — LIFO

Definizione (pila, LIFO). Last In, First Out: esce per primo l'ultimo elemento inserito.

Operazione	Effetto
push(x)	inserisce x in cima
pop()	toglie e restituisce l'elemento in cima (errore se vuota)
top() / peek()	restituisce l'elemento in cima senza toglierlo
is_empty(), size()

Tutte $O(1)$ con una buona implementazione.

Esempio. Con pila = [], dopo pila.append(3) e pila.append(5), pila.pop() restituisce 5 e lascia pila == [3].

In Python

Una list usata solo in fondo è già una pila:

pila = []
pila.append(3)       # push
pila.append(5)
pila[-1]             # top: 5
pila.pop()           # pop: 5
len(pila) == 0       # is_empty

Come classe con interfaccia esplicita:

class Pila:
    def __init__(self):
        self._dati = []

    def push(self, x):
        self._dati.append(x)

    def pop(self):
        if not self._dati:
            raise IndexError("pop da pila vuota")
        return self._dati.pop()

    def top(self):
        if not self._dati:
            raise IndexError("pila vuota")
        return self._dati[-1]

    def __len__(self):
        return len(self._dati)

Applicazione: parentesi bilanciate

Definizione (controllo delle parentesi bilanciate con una pila)

def bilanciata(s):
    coppie = {")": "(", "]": "[", "}": "{"}
    pila = []
    for c in s:
        if c in "([{":
            pila.append(c)
        elif c in coppie:
            if not pila or pila.pop() != coppie[c]:
                return False
    return not pila           # alla fine non devono restare aperte

bilanciata("a[(b)+c]")        # True
bilanciata("(]")              # False

Esempio. bilanciata("a[(b)+c]") restituisce True, bilanciata("(]") restituisce False.

Altre applicazioni: lo stack delle chiamate di funzione (RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →), annulla/ripeti negli editor, valutazione di espressioni, trasformare una ricorsione in un ciclo.

In C, su array

#define CAP 100

typedef struct {
    int dati[CAP];
    int n;               /* numero di elementi; la cima è dati[n-1] */
} Pila;

void pila_init(Pila *p)          { p->n = 0; }
int  pila_vuota(const Pila *p)   { return p->n == 0; }

int pila_push(Pila *p, int x) {
    if (p->n == CAP) return 0;   /* piena: fallimento */
    p->dati[p->n++] = x;
    return 1;
}

int pila_pop(Pila *p, int *x) {
    if (p->n == 0) return 0;     /* vuota */
    *x = p->dati[--p->n];
    return 1;
}

Capacità fissa; per farla crescere si usa realloc come nell'array dinamico di Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →, oppure una lista concatenataLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate → con inserimento e rimozione in testa.

Coda (queue) — FIFO

Definizione (coda, FIFO). First In, First Out: esce per primo l'elemento inserito da più tempo.

Operazione	Effetto
enqueue(x)	inserisce in fondo
dequeue()	toglie e restituisce il primo (errore se vuota)
first()	restituisce il primo senza toglierlo
is_empty(), size()

Esempio. Con coda = deque(), dopo append("a") e append("b"), popleft() restituisce 'a' e coda[0] vale 'b'.

In Python

list.pop(0) costa $O(n)$ (sposta tutti gli elementi): per una coda si usa collections.deque, con inserimento e rimozione $O(1)$ a entrambi gli estremi.

from collections import deque
coda = deque()
coda.append("a")       # enqueue
coda.append("b")
coda.popleft()         # dequeue: 'a'
coda[0]                # first: 'b'

Applicazioni: gestione di richieste nell'ordine di arrivo (buffer di pacchetti, stampanti, processi pronti nel sistema operativo), visita in ampiezza di grafi e alberi, simulazioni.

In C: coda circolare su array

Definizione (coda circolare su array). Due indici, testa (primo elemento) e numero di elementi n; le posizioni "girano" con il modulo, così non serve spostare elementi.

Esempio. Con CAP = 8, testa = 6 e n = 3, enqueue scrive in $(6+3)\bmod8=1$; dopo un dequeue si ha testa = (6 + 1) % 8 = 7.

#define CAP 8

typedef struct {
    int dati[CAP];
    int testa;           /* indice del primo elemento */
    int n;               /* elementi presenti */
} Coda;

void coda_init(Coda *q) { q->testa = 0; q->n = 0; }

int coda_enqueue(Coda *q, int x) {
    if (q->n == CAP) return 0;
    q->dati[(q->testa + q->n) % CAP] = x;    /* prima posizione libera */
    q->n++;
    return 1;
}

int coda_dequeue(Coda *q, int *x) {
    if (q->n == 0) return 0;
    *x = q->dati[q->testa];
    q->testa = (q->testa + 1) % CAP;
    q->n--;
    return 1;
}

Tutte le operazioni sono $O(1)$.

Errori tipici

• Usare list.pop(0) / insert(0, x) per una coda grande in Python: costo quadratico complessivo.
• Non controllare pila o coda vuota prima di pop/dequeue.
• Nella coda circolare, distinguere "piena" e "vuota" solo con testa == coda: senza un contatore (o una cella lasciata vuota) i due casi coincidono.