Informatica I - L'ADT Pila

Concetti base di una pila (stack)

In una pila (stack) gli oggetti possono essere inseriti ed estratti secondo un comportamento definito LIFO (Last In, First Out): l'ultimo oggetto inserito è il primo ad essere estratto. L’unico oggetto che può essere ispezionato è quello che si trova in cima alla pila. Per realizzare una pila si usa una struttura di tipo array "riempito solo in parte".

Operazioni principali della pila

Le operazioni (metodi) che caratterizzano una pila sono:

• Push: inserisce un oggetto in cima alla pila.
  Sintassi:

  public interface Stack extends Container { void push(Object obj); }

• Pop: elimina l’oggetto che si trova in cima alla pila.
  Object pop();
• Top: ispeziona l’oggetto in cima alla pila senza estrarlo.
  Object top();

Metodi comuni ai container

Inoltre, una pila (come ogni Container) ha i metodi:

• Size: per sapere quanti oggetti ci sono nel contenitore.
• IsEmpty: per sapere se il contenitore è vuoto.

Pile nella Java Virtual Machine

Ciascun programma Java in esecuzione ha una propria pila chiamata Java Stack che viene usata per mantenere traccia delle variabili locali, dei parametri formali dei metodi e di altre importanti informazioni relative ai metodi, man mano che questi sono invocati. I descrittori sono denominati Frame. A un certo istante durante l'esecuzione, ciascun metodo sospeso ha un frame nel Java Stack.

Prestazioni e analisi ammortizzata dei metodi di una pila

L’analisi ammortizzata si usa per mostrare che, in una sequenza di operazioni, il costo medio di un’operazione è piccolo, anche se una singola operazione della sequenza è “costosa”. È diversa dall'analisi di caso medio vista in precedenza:

• Analisi di caso medio: si basa su stime statistiche dell'input.
• Analisi ammortizzata: fornisce il costo medio di una singola operazione nel caso peggiore.

Analisi aggregata

Ci sono varie tecniche di analisi ammortizzata:

• Si stima il tempo T(n) per una sequenza di n operazioni, nel caso peggiore. Allora il tempo medio per una operazione è T(n)/n.
• Applichiamo questa tecnica all'analisi dei tempi di esecuzione dei metodi di inserimento in strutture dati.

Il tempo di esecuzione di ogni operazione su una pila senza ridimensionamento è costante, cioè non dipende dalla dimensione n della struttura dati stessa (non ci sono cicli), e vale O(1).

Analisi dei tempi di esecuzione con ridimensionamento

L’unica differenza con una pila senza ridimensionamento è l’operazione push: “Alcune volte” push richiede un tempo O(n) (perché all’interno del metodo resize è necessario copiare tutti gli n elementi nel nuovo array).