Pile (Struttura Dati)

---

Index

1. Definizione
2. Operazioni
3. Push
4. Pop

Related

• Introduzione agli Algoritmi (class)
• Strutture Dati

---

Definizione

La Pila è una struttura dati che esibisce un comportamento LIFO (Last In First Out)

LIFO

Gli elementi vengono prelevati dalla pila nell’ordine inverso rispetto a quello col quale vi sono stati inseriti.

---

Operazioni

Su una Pila sono definite solo due operazioni:

• Inserimento (Push)
• Estrazione (Pop)

Top

Per garantire la proprietà LIFO le operazioni Push e Pop operano sulla stessa estremità della pila (attraverso il puntatore top)

---

Push (inserimento)

Implementazione lista python

def push(Pila, x):
  Pila.append(x)

costo: $\theta (1)$

Implementazione linked list

Riceve il puntatore alla cima della pila ed il valore da inserire, lo inserisce in un nodo in cima alla lista puntata e restituisce la nuova cima

def push(top, x):
  return Nodo(x, top)

Costo: $\Theta (1)$

Risultato operazione top = push(top, 3):

---

Pop (estrazione)

Implementazione lista python

def pop(Pila):
  if Pila = []: 
  	return None
  return Pila.pop()

costo: $\theta (1)$

Implementazione linked list

Prende il puntatore alla cima della pila e restituisce il valore del nodo in cima alla pila e la nuova cima della pila.

def pop(top):
  if pop == None:
  	return None, None
  return top.key, top.next

Costo: $\Theta (1)$

Risultato operazione x, top = pop(top):

---