Esercizio 11pila di code

Esame

In questa pagina 4

Testo (appello del 13 settembre 2017 di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java, qui in Python).

Una pila di code è una struttura che annida le caratteristiche dei due ADT pila e coda, con l'interfaccia:

operazione	significato
`push(x)`	inserisce l'oggetto nella coda che si trova in cima alla pila
`pop()`	restituisce ed elimina l'oggetto inserito per primo nella coda in cima alla pila
`top()`	come `pop()` ma senza eliminarlo
`size()`	numero di elementi contenuti nella pila di code
`is_empty()`	vero se la pila di code è vuota

Esempio: gli elementi $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ da inserire, con code di taglia $3$ , finiscono così: $A = \{1, 2, 3\}$ , $B = \{4, 5, 6\}$ , $C = \{7, 8, 9\}$ . Estraendo tutti gli elementi l'ordine è $\{7, 8, 9, 4, 5, 6, 1, 2, 3\}$ . Con $21$ elementi la pila è composta da $7$ code da $3$ .

Scrivere la classe MiaPilaDiCode che realizza l'interfaccia, con code di taglia massima 3.
Scrivere un programma di prova che crea una MiaPilaDiCode, legge il file input.txt inserendo ogni riga nella pila di code, poi estrae tutti gli elementi mostrandoli sullo standard output.

Teoria: Pila e coda, Classi ed ereditarietà in Python, Realizzare contenitori su array e liste.

Idea: ADT costruito sopra altri due ADT

Non serve un array: la struttura si ottiene componendo una pila e delle code (vedi Realizzare contenitori su array e liste).

La pila è una list usata solo in fondo (append, pop); i suoi elementi sono code (collections.deque, con append in fondo e popleft dall'inizio).
push(x): se non c'è nessuna coda, o quella in cima ha già 3 elementi, si apre una nuova coda in cima; poi x si accoda in fondo alla coda in cima.
pop(): si toglie con popleft il primo elemento della coda in cima (il più vecchio di quella coda); se la coda si svuota, va rimossa dalla pila: altrimenti top e push guarderebbero una coda vuota.
top() legge code[-1][0]; size si tiene con un contatore (sommare le lunghezze costerebbe $O(\text{numero di code})$ ).

Tutte le operazioni sono $O(1)$ .

python

from collections import deque

class MiaPilaDiCode:
    """Pila le cui celle sono code di taglia massima K (qui 3)."""
    K = 3

    def __init__(self):
        self._code = []                      # pila di deque: la cima è l'ultima
        self._n = 0

    def push(self, x):
        if not self._code or len(self._code[-1]) == self.K:    # nessuna coda o coda in cima piena
            self._code.append(deque())
        self._code[-1].append(x)                               # in fondo alla coda in cima
        self._n += 1

    def pop(self):
        x = self.top()
        self._code[-1].popleft()                               # esce il PRIMO inserito della coda in cima
        if not self._code[-1]:
            self._code.pop()                                   # coda esaurita: si toglie dalla pila
        self._n -= 1
        return x

    def top(self):
        if self._n == 0:
            raise IndexError("pila di code vuota")
        return self._code[-1][0]

    def size(self):
        return self._n

    def is_empty(self):
        return self._n == 0

Programma di prova

python

import io

def main(f):
    p = MiaPilaDiCode()
    for riga in f:
        p.push(riga.rstrip("\n"))        # ogni riga del file nella pila di code
    while not p.is_empty():
        print(p.pop())

main(io.StringIO("a\nb\nc\nd\ne\n"))     # con il file vero: main(open("input.txt"))

Con le righe a b c d e (taglia 3) le code sono $A = \{a, b, c\}$ e $B = \{d, e\}$ : stampa d, e, a, b, c.

Verifica

python

p = MiaPilaDiCode()
for i in range(1, 10):
    p.push(i)
print([len(c) for c in p._code], p.top(), p.size())     # [3, 3, 3] 7 9
usciti = []
while not p.is_empty():
    usciti.append(p.pop())
print(usciti)                                           # [7, 8, 9, 4, 5, 6, 1, 2, 3]
assert usciti == [7, 8, 9, 4, 5, 6, 1, 2, 3]

p = MiaPilaDiCode()
for i in range(21):
    p.push(i)
print(len(p._code))                                     # 7 code da 3

p = MiaPilaDiCode()
for i in range(1, 5):                                   # code: [1,2,3] [4]
    p.push(i)
print(p.pop(), p.pop(), p.pop(), p.pop())               # 4 1 2 3

for i in (1, 2, 3, 4):
    p.push(i)                                           # [1,2,3] [4]
p.pop()                                                 # esce 4: la coda [4] viene eliminata
p.push(9)                                               # la coda in cima è piena -> ne apre una nuova
print([list(c) for c in p._code])                       # [[1, 2, 3], [9]]

Errori comuni

Non eliminare la coda svuotata: top() darebbe IndexError pur con elementi nelle code sotto.
Estrarre dalla fine della coda (comportamento da pila) invece che dall'inizio (da coda).
Aprire una nuova coda a ogni push, o solo quando la pila è vuota, ignorando la taglia massima.
Contare gli elementi con len(self._code) (numero di code) invece che con un contatore.
Ricostruire la struttura dopo ogni operazione: costo $O(n)$ inutile.

Versione ripasso

Appello del 13 settembre 2017 (UniPD, in Java; adattato a Python). Teoria: Pila e coda, Realizzare contenitori su array e liste.

Interfaccia: push(x) nella coda in cima; pop()/top() primo inserito della coda in cima; size, is_empty. Taglia massima 3: $1\ldots 9$ → $\{1,2,3\}$ , $\{4,5,6\}$ , $\{7,8,9\}$ ; estrazione $7,8,9,4,5,6,1,2,3$ .

Struttura: list di deque (la cima è l'ultima).

push: se non ci sono code o la coda in cima ha 3 elementi, append(deque()); poi append(x) alla coda in cima.
pop: popleft sulla coda in cima; se si svuota, pop dalla pila.
top: code[-1][0]; contatore _n per size. Tutto $O(1)$ .

Prova: leggere input.txt riga per riga con push, poi pop fino a vuoto.

Errori comuni: coda vuota non eliminata; estrazione dalla fine; nuova coda a ogni push; size come numero di code.

Esercizio 11pila di code

Idea: ADT costruito sopra altri due ADT

Programma di prova

Verifica

Errori comuni

Teoria collegata