File UniqueQueue.h

↰ Parent directory (ADS/queue)

A QUEUE [see File ADT.h] with no duplicates, beyond the book, with one of two policies for an item that is already in the queue: IGNORE_NEW does not enqueue it again, FORGET_OLD removes the old copy and enqueues the item at the back.

Definition (`ADS/queue/UniqueQueue.h`)

Program Listing for File UniqueQueue.h

Detailed Description

The items are kept in a List [see File List.h], so that enqueue() takes O( n ) time for the search of the copy and the other operations O( 1 ).

The contracts [see File Contract.h]: top() and dequeue() need a queue that is not empty; enqueue() ensures that the item is in the queue, at the back with FORGET_OLD; the invariant is that no item occurs twice. The operations are defined in UniqueQueue.tpp.