Code

I valori memorizzati nella coda sono dello stesso tipo. I nuovi valori vengono aggiunti in fondo alla coda, e un’estrazione restituisce il primo valore. La coda è una struttura di tipo FIFO, ovvero First In First Out. Il primo che entra è il primo che esce.

Il nodo dello stack è equivalente a quello delle Liste. La coda però è rappresentata da un nodo speciale, composto da due puntatori: head e tail, che puntano rispettivamente alla testa e alla coda della coda.

Primitive

1. new_queue(): crea una nuova coda vuota - $\Theta (1)$
2. is_empty_queue(Q): ritorna true se la coda è vuota - $\Theta (1)$
3. enqueue(Q, x): accoda il nodo x alla coda Q - $\Theta (n)$
4. first(Q): ritorna l’elemento di testa della coda, ma non lo elimina - $\Theta (1)$
5. dequeue(Q): ritorna l’elemento di testa della coda e lo elimina - $\Theta (1)$

new_queue():
	Q := new_queue_node()
	Q.head := nil
	Q.tail := nil
	return Q

is_empty_queue(Q):
	return Q.head == nil

enqueue(Q, x):
	e := new_queue_node()
	e.val = x
	e.next = nil
	if is_empty_queue(Q) then
		Q.head = e
	else
		Q.tail.next = e
	Q.tail = e

first(Q):
	if not is_empty_queue(Q) then
		return Q.head.val

dequeue(Q):
	if not is_empty_queue(Q) then
		tmp := first(Q)
		Q.head = Q.head.next
		if Q.head == nil then
			Q.tail = nil
		return tmp
	return nil

asd_18