For efficiency, we implement a queue as two pointers to lists.
struct _Queue { struct List *head; struct List *tail; };
head
is a pointer to a list, which represents the entire queue.
tail
is a pointer to a list, but this list represents the
last link (to an empty list) of the queue. In other words,
List_isempty(q->tail)
should always be false, given that
q
points to a valid struct _Queue
.
Note that tail
points to the rest
data member of the last
struct _Listnode
in a list when a queue is not empty. When a queue is
empty, however, tail
points to the list that head
points
to.