Per garantisce la proprietà FIFO l’operazione Enqueue opera su una estremità della coda (tail) e la Dequeue opera sull’altra estremità (head)
Enqueue (inserimento)
Implementazione lista python
def Inserimento(Coda, x): Coda.append(x)
Costo: θ(1)
Implementazione linked list
Prende in input i puntatori alla testa e alla coda ed il valore da inserire e dopo aver inserito il nodo col nuovo valore in coda restituisce i puntatori alla testa ed alla coda
def Inserimento(testa, coda, x): p = Nodo(x) if coda == None return p, p coda.next = p return testa, p
Costo: Θ(1)
Risultato operazione p = inserimento(testa, coda, 3):
Dequeue (estrazione)
Implementazione lista python
def Estrazione(Cosa): if Pila = []: return None return Pila.pop(0)
costo: θ(n)
Implementazione linked list
Prende in input i puntatori alla testa e alla coda e dopo aver estratto il valore del nodo in testa lo restituisce con i puntatori alla testa ed alla coda
def Estrazione(testa, coda): if testa == None: # Caso len = 0 return None, None, None if testa == coda: # Caso len = 1 return testa.key, None, None return testa.key, testa.next, coda # Caso len > 1
