Paola Magillo, Univestita' di Genova, Corso di Programmazione II per SMID, a.a. 2004-2005.

Lezione 10:

TIPI DI DATI, PILA E CODA

Tipi di dati concreti e astratti

Tipo di dati (concreto) =

un tipo, corrispondente a un insieme di valori
un insieme di operazioni (o funzioni) su di essi, che possono prendere come argomenti e/o restituire valori dello stesso tipo o di altri tipi

Un tipo di dati concreto e' come una classe in Java:

come sono fatti i valori = gli attributi
come sono fatte e che cosa fanno le operazioni = i metodi (dichiarazione e implementazione)

Esempio: i numeri interi con le operazioni di addizione, sottrazione, moltiplicazione, divisione e controllo se un numero sia divisibile per un altro numero (quest'ultima restituisce un booleano).

Notazione:

Tipi: integer, boolean
Operazioni:
  add: integer x integer --> integer definita come add(x,y) = x+y
  sub: integer x integer --> integer definita come sub(x,y) = x-y
  mul: integer x integer --> integer definita come mul(x,y) = x*y
  div: integer x integer --> integer definita come div(x,y) = x/y
  checkdiv: integer x integer --> boolean definita come
            checkdiv(x,y) = true  iff  y*div(x,y) = x

Tipo di dati astratto = astrazione di un tipo di dati:

del tipo viene dato solo il nome, non viene precisato l'insieme di valori corrispondente
vengono dati solo i nomi delle operazioni con i tipi degli argomenti e del risultato, senza precisare che cosa fanno esattamente
vengono pero' date delle proprieta' che le operazioni devono soddisfare

A parte le proprieta', un tipo di dati astratto e' come un'interfaccia in Java:

niente attributi = non diciamo come sono fatti i tipi
solo la dichiarazione e non l'implementazione delle funzioni = dichiamo come sono fatte ma non che cosa fanno esattamente

In pratica un tipo di dati astratti e' la specifica dei requisiti che vogliamo che un tipo di dati concreto possegga.

Matematicamente si tratta di un'algebra eterogenea.

Un tipo di dati astratto puo' essere implementato da uno o piu' tipi di dati concreti.
L'implementazione fornisce gli insiemi corrispondenti ai nomi dei tipi e il body alle operazioni, nel rispetto delle proprieta'.

Esempio

Tipo di dati astratto che prevede:

un tipo: QUALCOSA
due funzioni unarie: VAI e TORNA
con le proprieta' che VAI e TORNA siano inverse

Tipi: QUALCOSA
Operazioni: 
  VAI: QUALCOSA --> QUALCOSA
  TORNA: QUALCOSA --> QUALCOSA
Proprieta':
  VAI(TORNA(x))==x
  TORNA(VAI(x))==x

Per illustrare graficamente i tipi e le operazioni si puo' fare diagramma a bolle...

Questo tipo di dati astratto puo' essere implementato dal tipo di dati concreto [1]:

 QUALCOSA = i numeri interi
 VAI(x) = x+1
 TORNA(x) = x-1

Ma anche dal tipo di dati concreto [2]:

 QUALCOSA = i booleani
 VAI(x) = not x
 TORNA(x) = VAI(x)

Oppure dal tipo di dati concreto [3]:

 QUALCOSA = i mesi dell'anno
 VAI(x) = il mese successivo a x
 TORNA(x) = il mese precedente a x

E da infiniti altri...

Dall'astratto al concreto

Esistono livelli intermedi fra l'astratto e il concreto.
Per es. se dico che QUALCOSA devono essere gli interi ho ancora gradi di liberta' per le operazioni VAI e TORNA (per es. entrambe potrebbero essere il cambiamento di segno, oppure una somma 10 e l'altra lo sottrae...).
In Java sarebbe una classe astratta.

Cio' che e' concreto per la matematica e' ancora astratto e per l'informatica. Per l'informatica e' concreto davvero solo quando e' codice funzionante!
Per es. considerando l'implementazione [3] del tipo di dati astratto QUALCOSA, prima bisogna stabilire come rappresentiamo i mesi (es. con gli interi da 1 a 12, oppure con 12 stringhe che sono i loro nomi in italiano) e poi scrivere il codice in un linguaggio (es. in Java una classe).

Anche quando un'operazione dal punto di vista matematico e' univocamente definita, puo' non essere univocamente determinato l'algoritmo da usare per scriverne il codice. La definizione matematica dice solo che cosa deve fare un'operazione, non dice come la deve fare.
Esempio: l'operazione di ordinare in modo crescente una sequenza di numeri interi e' univocamente definita, ma esistono numerosi algoritmi di ordinamento e ne devo scegliere uno.

Sviluppo del Software

1. Descrizione informale del problema da parte del committente
Es: c'e' un insieme di pazienti con delle malattie a cui sono prescritte delle medicine...

2. Estrapolazione della specifica dei requisiti (tipo di dati astratto)
Es: di un paziente devo poter ottenere nome, cognome, eta', malattie che ha, medicine che prende; di una malattia devo poter ottenere le medicine che servono a curarla; di una medicina devo poter ottenere le malattie che puo' curare.

3. Implementazione per tappe successive:

la struttura dati, cioe' come sono fatti i valori, nell'es. quali informazioni tenere per il paziente (nome e cognome, eta', lista di malattie, lista di medicine), ecc.
come li memorizziamo (nome e cognome sono stringe, ecc.)
gli algoritmi per le operazioni
fino alla scrittura del codice (classi Java).

Tipi di dati Pila e Coda

Una lista di elementi (un tipo base qualsiasi, per es. i numeri interi) e' una sequenza finita di elementi. Ma quali operazioni vogliamo che siano possibili su queste sequenze?

Pila e Coda sono due diversi tipi di dati aventi come insieme di valori corrispondenti le sequenze finite di elementi.

Entrambe prevedono operazioni di:

creazione della pila / coda vuota
controllo se la pila / coda e' vuota
aggiunta di un elemento (in che posizione, e' da stabilirsi)
cancellazione di un elemento (quale, e' da stabilirsi), se la pila / coda non e' vuota
lettura dell'elemento che sarebbe cancellato senza cancellarlo, se la pila / coda non e' vuota

La differenza sta nelle proprieta' richieste per queste operazioni.

Pila (Stack)

Si mettono e tolgono elementi dalla stessa parte della sequenza, per es. la cima.

l'aggiunta avviene in cima
la cancellazione cancella l'elemento in cima (l'ultimo inserito)

Realizza la politica FILO (First In Last Out): il primo aggiunto viene cancellato per ultimo.

Tipi: stack, element, boolean
Operazioni:
  push: stack x element --> stack
  pop: stack --> stack
  top: stack --> element
  empty: --> stack
  isempty: stack --> boolean
Proprieta':
  top(push(st,el)) = el
  pop(push(st,el)) = st
  isempty(empty)
  not isempty(push(st,el))

Traducendo in java (non possiamo tradurre le proprieta'), usiamo come "element" la classe generica Object e scriviamo un'interfaccia Stack:

interface Stack
{
  void push(Object o);
  void pop();
  Object top();
  void empty();
  boolean isEmpty();
}

Coda (Queue)

Si mettono e tolgono elementi da parti opposte della sequenza, per es. in cima e in fondo.

l'aggiunta avviene in cima
la cancellazione cancella l'elemento in fondo (il primo inserito)

Realizza la politica FIFO (First In First Out): il primo aggiunto viene cancellato per primo.

Tipi: queue, element, boolean
Operazioni:
  enqueue: queue x element --> queue
  dequeue: queue --> queue
  front: queue --> element
  empty: --> queue
  isempty: queue --> boolean
Proprieta':
  front(qu) = front(enqueue(qu,el))
  dequeue(enqueue(qu,el)) = enqueue(dequeue(qu),el)
  isempty(empty)
  not isempty(enqueue(qu,el))

Traducendo in Java (tranne le proprieta'):

interface Queue
{
  void enqueue(Object o);
  void dequeue();
  Object front();
  void empty();
  boolean isEmpty();
}

Implementazioni

I tipi di dati Pila e Coda concettualmente sono univocamente definiti dalle proprieta' che abbiamo posto, ma devono essere ancora implementati in una struttura dati (i valori) e algoritmi (le operazioni), e poi struttura dati ed algoritmi vanno implementati in codice di un linguaggio di programmazione (es. Java).

Per la struttura dati abbiamo varie possibilita'... possiamo usare come struttura dati di base:

un array: la pila / coda ha una capacita' limitata, puo' contenere al massimo tanti elelenti quante sono le caselle dell'array.
una lista linkata: la pila / coda ha capacita' illimitata.

Lista linkata = struttura formata da celle, ognuna delle quali puo' contenere un elemento e ha puntatore alla cella successiva (link = collegamento).
Il treno della lezione 3 e poi la classe IntList della lezione 4 era una lista linkata di interi!

Per gli algoritmi, abbiamo il seguente obiettivo: fare si' che tutte le operazioni siano implementate eseguendo un numero costante di istruzioni, indipendentemente da quanti elementi sono presenti nella pila / coda.

Implementazione della pila con array

Elementi della pila sono messi in posizioni consecutive nell'array, in ordine inverso (fondo della pila = prima casella dell'array, cima della pila = ultima casella dell'array).
L'array si espande e si contrae dalla parte della cima, cioe' dalla parte della fine dell'array (aggiungere elemento sposta la cima verso destra, toglierlo la sposta verso sinistra). Il fondo della pila resta stabile, coincidente con l'inizio dell'array.
Un contatore cont tiene il numero di caselle occupate (il numero di elementi nella pila), che sono dalla posizione 0 a cont-1.
Il valore di cont e' anche la posizione della prima casella libera.
La pila ha raggiunto la sua massima capacita' sse l'array e' pieno sse cont e' uguale alla lunghezza dell'array.

Implementazione delle operazioni:

Pila vuota (empty): azzerare il contatore cont
Controllo se pila e' vuota (isempty): vedere se contatore e' zero
Aggiunta di elemento in cima (push), se non eccede la capacita': mette l'elemento nella casella di posizione cont, incrementa cont.
Restituzione dell'elemento in cima (top): restituisce il contenuto della casella di posizione cont-1.
Cancellazione dell'elemento in cima (pop): decrementa cont.

Implementazione della pila con "lista linkata"

La pila ha puntatore alla prima cella di lista linkata contenente i suoi elementi nell'ordine dalla cima al fondo.

Implementazione delle operazioni:

Pila vuota (empty): nessuna cella, la prima cella e' null
Controllo se pila e' vuota (isempty): vedere se la prima cella e' null
Aggiunta di elemento in cima (push): crea nuova cella con l'elemento, l'attuale prima cella diventa la successiva di questa nuova e questa nuova diventa la prima cella.
Restituzione dell'elemento in cima (top): restituisce il contenuto della prima cella.
Cancellazione dell'elemento in cima (pop): l'attuale prima cella viene eliminata, la sua successiva diventa la prima cella.

Implementazione della coda con array

Elementi della coda sono messi in posizioni consecutive nell'array, nel loro ordine. Inizialmente cima = prima casella, fondo = ultima casella dell'array.
L'array si espande verso il fondo (ultima casella si sposta verso destra) e si contrae dalla parte della cima (prima casella si sposta anch'essa verso detra).
L'array e' considerato "circolare" cioe' l'ultima casella dell'array ha come successiva la prima (questo equivale a fare tutte gli incrementi sugli indici dell'array modulo la lunghezza dell'array).
Poiche' aggiunge in fondo e si toglie in cima, a un certo punto puo' scavalcare la fine dell'array...
Tengo due contatori: la posizione dell'elemento in cima e in fondo.
Per comodita' tengo anche contatore cont del numero di elementi presenti. La coda ha raggiunto la sua massima capacita' sse cont e' uguale alla lunghezza dell'array.

Implementazione delle operazioni:

Coda vuota (empty): assegna cont = 0 e a cima e fondo due valori tali che il successivo (modulo la lunghezza dell'array) di fondo sia uguale a cima (es. cima=0 e fondo=lunghezza-1)

Controllo se coda e' vuota (isempty): vedere se cont e' zero
Aggiunta di elemento in fondo (enqueue), se non eccede la capacita': mette l'elemento nella casella di posizione fondo+1, incrementa fondo, incrementa cont.
Restituzione dell'elemento in cima (front): restituisce il contenuto della casella di posizione cima.
Cancellazione dell'elemento in cima (dequeue): incrementa cima, decrementa cont.

Nota: Tutte le somme che coinvolgono le variabili cima e fondo sono intese modulo la lunghezza dell'array.

Implementazione della coda con "lista linkata"

La coda ha puntatore alla prima cella e all'ultima cella di lista linkata contenente i suoi elementi nell'ordine dalla cima al fondo.

Implementazione delle operazioni:

Coda vuota (empty): nessuna cella, la prima cella (e anche l'ultima ma basta controllarne una) e' null
Controllo se coda e' vuota (isempty): vedere se la prima cella e' null
Aggiunta di elemento in fondo (enqueue): crea nuova cella con l'elemento, che viene inserita come successiva dell'attuale ultima cella, questa nuova diventa l'ultima cella.
Restituzione dell'elemento in cima (front): restituisce il contenuto della prima cella.
Cancellazione dell'elemento in cima (dequeue): l'attuale prima cella viene eliminata, la sua successiva diventa la prima cella.

Quando le operazioni non sono possibili

Possiamo seguire due strategie:

generare errore (eccezione in Java)
non fare nulla e, se c'e' da restituire un risultato, restituire un valore speciale (es. restituire null)

Bisogna essere coerenti, usare sempre la stessa strategia!

Esempio di uso delle pile

Programma che, data una stringa con parentesi, controlla se le parentesi sono bilanciate. Le parentesi possono essere tonde (), quadre [], graffe {}.

Algoritmo:

Uso una pila, inizialmente vuota, come struttura ausiliaria.
Scorro la stringa, considerando solo i caratteri parentesi.
Sulla pila metto, man mano che le incontro, tutte le parentesi aperte.
Quando incontro una parentesi chiusa, guardo le la parentesi aperta in cima alla pila corrisponde al tipo di questa parentesi chiusa (tonda, quadra o graffa).
Se non corrisponde allora le parentesi non sono bilanciate, posso gia' rispondere NO.
Se corrisponde tolgo la parentesi aperta da in cima alla pila (e' stata eliminata dalla parentesi chiusa corrispondente) e vado avanti.
Quando ho finito di scorrere la stringa, se la pila non e' vuota allora le parentesi non sono bilanciate (delle parentesi aperte non sono state chiuse) e rispondo NO. Altrimenti le parentesi sono bilanciate e rispondo SI.

Vedere il programma ControllaParentesi.java. La stringa da controllare va scritta su command-line. Per esempio:

   java ControllaParentesi "[ci{ao}]"  -- rispondera' SI
   java ControllaParentesi "[ci{ao)}]" -- rispondera' NO

Serve anche l'interfaccia Stack (vista in questa lezione) e la classe ArrayStack che la implementa (provate a scriverla voi in base alle indicazioni viste in questa lezione).