Algoritmi e strutture dati - Specifiche: Pile

Torna alla pagina di Algoritmi e strutture dati

---

 :: Algoritmi e strutture dati - Specifiche ::

Pile

---

Sintassi

• creapila: () -> pila
  Crea ed inizializza una pila alla sequenza vuota.
• pilavuota: (pila) -> booleano
  Restituisce vero o falso a seconda che la pila sia vuota o no.
• leggipila: (pila) -> tipoelem
  Legge il valore dell'elemento in testa alla pila.
• fuoripila: (pila) -> pila
  Elimina l'elemento che si trova in testa alla pila.
• inpila: (tipoelem, pila) -> pila
  Aggiunge un elemento in testa alla pila.

Semantica

• creapila() = P'
  Post: P' = Λ
• pilavuota(P) = b
  Post: b = vero, se P = Λ; b = falso altrimenti
• leggipila(P) = a
  Pre: P = a₁, a₂, ... , a_n con n≥1
  Post: a = a₁
• fuoripila(P) = P'
  Pre: P = a₁, a₂, ... , a_n con n≥1
  Post: P' = a₂, a₃, ... , a_n se n>1, P' = Λ se n=1
• inpila(a, P) = P'
  Pre: P = a₁, a₂, ... , a_n con n≥0
  Post: P' = a, a₁, a₂, ... , a_n

Implementazione in C++

Realizzazione con vettore

#define MAXL 100

typedef struct _pila {
   int testa;
   tipoelem elementi[MAXL];
} pila;

pila P;

• creapila:
  

  
  void creapila (pila *P) {
     P->testa = 0;
  }
  
• pilavuota:
  

  
  boolean pilavuota (pila *P) {
     return (P->testa == 0;
  }
  
• leggipila:
  

  
  tipoelem pilavuota (pila *P) {
     if( !pilavuota(P))
        return (P->elementi[P->testa-1]);
  }
  
• fuoripila:
  

  
  void fuoripila (pila *P) {
     if( !pilavuota(P))
        P->testa--;
  }
  
• inpila:
  

  
  tipoelem inpila (tipoelem a, pila *P) {
     if( P->testa == MAXL)
        printf("Pila piena\n");
     else {
        P->elementi[P->testa] = a;
        P->testa++;
     }
  }
  

---

Torna alla pagina di Algoritmi e strutture dati