5.2 Queue

Although it is possible to implement a queue with just a basic list interface as discussed in module 0043, it is often better to implement a queue as ``sort-of-two'' lists. This is because with a queue, we remove at the beginning of the list, but we insert at the end of a list. We can, if we want to, traverse to the end of a list and insert an item. However, this means the time required to insert an item is proportional to the number of items in a list.

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.