G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione XXIII
Il tipo di dato astratto stack
Programmazione di Calcolatori: il tipo di dato astratto stack
1
G. Amodeo,
C. Gaibisso
Lo stack
• L’idea:
LIFO: Last In First Out
Programmazione di Calcolatori: il tipo di dato astratto stack
2
G. Amodeo,
C. Gaibisso
Lo stack
• Possibile impiego (tra gli altri):
- gestione del processo di costruzione
incrementale di soluzioni tipico del
backtracking
• Backtracking:
- tecnica algoritmica basata sulla costruzione
incrementale di soluzioni attraverso una
sequenza di scelte
- se una scelta si rivela non corretta la
costruzione della soluzione riprende
dall’ultimo punto di decisione che offre
almeno un’alternativa alla scelta che ha
generato il fallimento (backtrack)
Programmazione di Calcolatori: il tipo di dato astratto stack
3
G. Amodeo,
C. Gaibisso
Gli stack di valori di tipo T (StackT)
• Modello:
sequenza di elementi di tipo T, o più
formalmente
StackT  <a1, a2, …, an>, aiT, i = 1, …, n
• Operazioni
a) InitStack:  StackT
Valore:
alcuno
Effetto:
InitStack()  <>
Programmazione di Calcolatori: il tipo di dato astratto stack
4
G. Amodeo,
C. Gaibisso
Gli stack di valori di tipo T
b) Push:
Valore:
StackT x T StackT
alcuno
Effetto: Push(<a1, …, an>, a)  <a1, …, an, a>
Esempio:
8
Push(<3, 1, 4>, 8)  < 3, 1, 4, 8>
4
1
3
Programmazione di Calcolatori: il tipo di dato astratto stack
5
G. Amodeo,
C. Gaibisso
Gli stack di valori di tipo T
c) Top:
Valore:
StackT  T
Top(<a1, …, an-1, an>) = an
Effetto: alcuno
Esempio:
Top(<3, 1, 4>) = 4
4
1
3
Programmazione di Calcolatori: il tipo di dato astratto stack
6
G. Amodeo,
C. Gaibisso
Gli stack di valori di tipo T
d) Pop:
Valore:
StackT  StackT x T
Pop(<a1, …, an-1, an>) = an
Effetto: Pop(<a1, …, an-1, an>)  <a1, …, an-1>
Esempio:
Pop(<3, 1, 4>) = 4
4
1
3
Programmazione di Calcolatori: il tipo di dato astratto stack
7
G. Amodeo,
C. Gaibisso
Gli stack di valori di tipo T
e) EmptyStack: StackT  Bool
Valore:
EmptyStack(<>) = True
EmptyStack(<a1, … >) = False
Effetto: alcuno
StackT  StackT
f) ResetStack:
Valore:
alcuno
Effetto: ResetStack(<a1, …, an-1, an>)  <>
Programmazione di Calcolatori: il tipo di dato astratto stack
8