Salta al contenuto
Note per Studenti Pila e coda

Pila e coda

In questa pagina 3

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

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)O(1) con una buona implementazione.

In Python

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

python
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:

python
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

python
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

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

c
#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

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()

In Python

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

python
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

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

c
#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)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.

Teoria collegata