Mazzi

Note

Un mazzo (coda a due fini, Dequeue) è una struttura dati che si comporta come un mazzo di carte, di cui ogni una contiene un elemento. È possibile aggiungere sia in testa che in coda alla struttura:

PushFront(Q,e): inserisce l'elemento e in testa al mazzo
PushBack(Q,e): inserisce l'elemento e in coda al mazzo
PopFront(Q): restituisce l'elemento in testa, cancellandolo
PopBack(Q): restituisce l'elemento in coda, cancellandolo
Empty(Q): restituisce true se il mazzo è vuoto

Implementazione con una lista doppiamente concatenata

Si ha che PushBack e PopFront si comportano come Enqueue e Dequeue di una coda realizzata con una lista, con l'aggiunta di:

PopBack(Q): restituisce tail.prev se diverso da head, rimuovendolo dalla lista
PushFront(Q,e): aggiunge l'elemento e in testa, aggiornando head e il suo successore
Empty(Q): restituisce head.next = tail

Implementazione con un vettore

Lo stoccaggio dei dati è effettuato in modo analogo alla coda semplice.
Si ha che PushBack e PopFront si comportano come Enqueue e Dequeue di una coda realizzata con un vettore, con l'aggiunta di:

PopBack(Q): se , restituisce A[tail] corrente, decrementa n, decrementa tail
PushFront(Q,e): , decrementa head, inserisce l'elemento e in A[head] e incrementa
Empty(Q): restituisce n = 0