Esercizio 12pila reversibile

Esame

In questa pagina 4

Testo (appello del 1° luglio 2025 di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD, canale C; adattato da un tema d'esame in Java, qui in Python).

Uno stack reversibile è definito dall'interfaccia

SR:  size(), is_empty(), top() -> eccezione StackEmptyException se vuoto,
     push(x), pop() -> eccezione StackEmptyException se vuoto, reverse()

in cui size, is_empty, top, push, pop hanno il solito significato e le solite prestazioni, mentre reverse() rovescia il contenuto dello stack: dopo la chiamata l'ultimo elemento inserito diventa il primo e il primo inserito diventa la testa dello stack. Una seconda chiamata di reverse() ripristina l'ordine iniziale. Dopo reverse(), push e pop inseriscono ed estraggono nel nuovo ordine.

Esempio: dato uno stack st inizialmente vuoto, dopo push("a"); push("b"); reverse(); push("c"); push("d") lo stack contiene la sequenza ["b", "a", "c", "d"] dove "d" è la testa; un pop() restituisce "d", e un ulteriore reverse() seguito da un pop() restituisce "b".

Scrivere una classe MioSR che realizza l'interfaccia in modo che lo stack non sia soggetto a overflow (nessuna capacità massima). Nella realizzazione non è consentito usare classi contenitore della libreria (nel tema: ArrayList, LinkedList, Vector, Stack; qui: list, deque...).
Scrivere un programma di prova che legge dallo standard input una sequenza di stringhe (una per riga), le inserisce in uno stack MioSR, rovescia lo stack, ne copia il contenuto in un secondo stack (estraendo dal primo e inserendo nel secondo) e svuota questo secondo stack scrivendo il contenuto sull'uscita: deve corrispondere a quanto letto dall'ingresso in senso inverso.

Teoria: Pila e coda, Liste concatenate, Realizzare contenitori su array e liste.

Idea

Rovesciare davvero lo stack a ogni reverse() costerebbe $O(n)$ . Si osserva che la sequenza non cambia: cambia da quale estremo si legge la testa.

Si memorizza la sequenza in una struttura con due estremi raggiungibili in $O(1)$ : una lista doppiamente concatenata con puntatori _primo e _ultimo (niente contenitori della libreria, nessun overflow: i nodi si creano uno per volta).
Un flag _invertito dice quale estremo è la testa: False → la testa è _ultimo; True → la testa è _primo.
push aggiunge un nodo dal lato della testa, pop e top lavorano su quel lato.
reverse() si limita a negare il flag: $O(1)$ .

Verifica sull'esempio. push("a"); push("b"): lista a ⇄ b, testa a destra (b). reverse(): flag True, testa a sinistra: la sequenza logica è b, a con testa a. push("c") aggiunge a sinistra: c ⇄ a ⇄ b; push("d"): d ⇄ c ⇄ a ⇄ b. Letta dalla coda verso la testa, cioè dal fondo dello stack: b, a, c, d con testa d, come nel testo. pop() toglie d da sinistra. reverse() riporta il flag a False: la testa è a destra, b: pop() restituisce "b".

Codice

python

import io

class StackEmptyException(Exception):
    """top o pop su uno stack vuoto"""


class MioSR:
    """Stack reversibile su lista doppiamente concatenata. push, pop, top, reverse: O(1)."""

    class _Nodo:
        __slots__ = ("val", "prec", "succ")
        def __init__(self, val):
            self.val, self.prec, self.succ = val, None, None

    def __init__(self):
        self._primo = self._ultimo = None
        self._n = 0
        self._invertito = False        # False: la cima è _ultimo; True: la cima è _primo

    def size(self):
        return self._n

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

    def push(self, x):
        nodo = self._Nodo(x)
        if self._n == 0:
            self._primo = self._ultimo = nodo
        elif not self._invertito:               # cima in fondo: si aggiunge dopo _ultimo
            nodo.prec, self._ultimo.succ = self._ultimo, nodo
            self._ultimo = nodo
        else:                                   # cima davanti: si aggiunge prima di _primo
            nodo.succ, self._primo.prec = self._primo, nodo
            self._primo = nodo
        self._n += 1

    def top(self):
        if self._n == 0:
            raise StackEmptyException("stack vuoto")
        return (self._primo if self._invertito else self._ultimo).val

    def pop(self):
        x = self.top()                          # solleva l'eccezione se vuoto
        if self._n == 1:
            self._primo = self._ultimo = None
        elif not self._invertito:
            self._ultimo = self._ultimo.prec
            self._ultimo.succ = None
        else:
            self._primo = self._primo.succ
            self._primo.prec = None
        self._n -= 1
        return x

    def reverse(self):
        self._invertito = not self._invertito   # O(1): cambia solo l'estremo che fa da cima


def main(f, out):
    uno = MioSR()
    for riga in f:
        uno.push(riga.rstrip("\n"))
    uno.reverse()                               # ora la cima è la prima riga letta
    due = MioSR()
    while not uno.is_empty():
        due.push(uno.pop())                     # copia: nel secondo stack la prima riga è sul fondo
    while not due.is_empty():
        print(due.pop(), file=out)


st = MioSR()
st.push("a"); st.push("b"); st.reverse(); st.push("c"); st.push("d")
print(st.size(), st.top())                      # 4 d
print(st.pop())                                 # d
st.reverse()
print(st.pop())                                 # b

uscita = io.StringIO()
main(io.StringIO("a\nb\nc\nd\n"), uscita)       # con la tastiera: main(sys.stdin, sys.stdout)
print(uscita.getvalue().split())                # ['d', 'c', 'b', 'a']

Perché l'uscita è l'inverso dell'ingresso. Dopo aver letto a b c d lo stack, dal fondo alla cima, è a b c d; reverse() lo rende d c b a con testa a. Estraendo dal primo si ottiene a, b, c, d e si inserisce in quest'ordine nel secondo: dal fondo a b c d, testa d. Svuotando il secondo si legge d, c, b, a.

Verifica con un modello

Si confronta MioSR con una list Python (reverse() del modello è list.reverse(), $O(n)$ ) su sequenze casuali di operazioni:

python

import random

for _ in range(500):
    s, modello = MioSR(), []
    for _ in range(100):
        op = random.choice(["push", "pop", "top", "rev"])
        if op == "push":
            x = random.random(); s.push(x); modello.append(x)
        elif op == "rev":
            s.reverse(); modello.reverse()
        else:
            try:
                r = s.pop() if op == "pop" else s.top()
            except StackEmptyException:
                assert not modello
                continue
            assert r == (modello.pop() if op == "pop" else modello[-1])
        assert s.size() == len(modello)
print("ok")

Errori comuni

Rovesciare fisicamente la lista a ogni reverse(): $O(n)$ , mentre l'interfaccia richiede le "solite prestazioni".
Usare un array di capacità fissa: l'interfaccia richiede assenza di overflow.
In pop con un solo elemento, non azzerare entrambi i puntatori _primo e _ultimo.
Dimenticare di aggiornare prec oltre a succ (e viceversa) nella lista doppiamente concatenata.
Applicare pop o top su stack vuoto senza sollevare StackEmptyException.

Versione ripasso

Appello del 1° luglio 2025 (UniPD, in Java; adattato a Python). Teoria: Pila e coda, Liste concatenate, Realizzare contenitori su array e liste.

Interfaccia: size, is_empty, top, push, pop (StackEmptyException se vuoto) e reverse() che rovescia il contenuto; due reverse() ripristinano. Esempio: push(a) push(b) reverse() push(c) push(d) → da fondo a testa b a c d; pop → d; reverse(); pop → b.

Soluzione: lista doppiamente concatenata (_primo, _ultimo, nessun overflow, nessun contenitore) + flag _invertito: False → la cima è _ultimo; True → la cima è _primo. push, pop, top lavorano sul lato della cima; reverse() nega il flag, $O(1)$ .

pop con un solo elemento: azzerare _primo e _ultimo.

Prova: leggere le righe in uno, uno.reverse(), copiare in due con due.push(uno.pop()), svuotare due → uscita = ingresso in senso inverso.

Errori comuni: rovesciare fisicamente la lista; array di capacità fissa; puntatori non azzerati con un solo elemento; prec e succ non coerenti; eccezione mancante.

Esercizio 12pila reversibile

Idea

Codice

Verifica con un modello

Errori comuni

Teoria collegata