|
|
Una pila (o stack) è una sequenza di elementi di un certo tipo, in cui è possibile aggiungere o togliere elementi soltanto ad un estremo (la testa della sequenza).
Una pila essere quindi vista come un caso speciale lista in cui l’ ultimo elemento è anche il primo ad essere rimosso e non è possibile accedere ad alcun elemento che non sia quello in testa. Tale meccanismo è detto LIFO, dall’ inglese “Last In First Out” , ovvero l ‘ultimo entrato è il primo ad uscire. Per esempio un tubetto di pastiglie ha un meccanismo di acceso LIFO, l’ultima inserita è la prima ad uscire.
Una coda è una sequenza di elementi di un certo tipo, in cui è possibile aggiungere elementi ad un estremo e toglierne dall’ estremo opposto.
Una coda può essere quindi vista come una particolare lista in cui è possibile aggiungere elementi ad un estremo (il fondo) e togliere elementi dall’ altro estremo (in testa). Tale meccanismo è detto
FIFO dall’ inglese “First In First Out”, ovvero il primo arrivato è il primo ad uscire. Per esempio una fila di persone ad uno sportello postale è gestita con la disciplina FIFO, il primo arrivato è il primo ad essere servito.
L’ insieme degli operatori tipici di una pila sono:
CREAPILA: per inizializzare la pila alla sequenza vuota
PILAVUOTA: per verificare che la pila sia vuota
LEGGIPILA: per leggere il valore dell’ elemento in testa ad una pila
FUORIPILA:per eliminare l’ elemento che si trova in testa alla pila
INPILA:per aggiungere un elemento in testa ad una pila
La specifica sintattica di questi operatori è la seguente:
Indichiamo con il termine ai gli elementi di una pila P, elementi di lunghezza arbitraria e di tipo tipoelem e sia b un booleano. Allora la specifica semantica della pila, sarà data dalle seguenti funzioni, con relative precondizioni e postcondizioni:
L’ insieme degli operatori tipici di una coda sono CREACODA, CODAVUOTA, LEGGICODA, FUORICODA E INCODA. Questi operatori hanno tutti le stesse specifiche sintattiche dei corrispettivi operatori per la pila. Per quanto riguarda le specifiche semantiche l’ unica differenza sta nell’ operatore INCODA. Indicando con Q una generica coda:
Poiché pile e code sono casi particolari di liste, ogni realizzazione scritta per le liste funziona anche per le pile e per le code:
Per saperne di più consulta i seguenti approfondimenti:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.