/* Implemenation of a queue as a linked data structure    */
/* Operations supported:                                  */
/* enqueue(x)       place item x at end of queue          */
/* head             return the item at head of queue      */
/* dequeue          remove next item from front of queue  */
/* empty            return true iff the queue is empty    */
/* Data structures:                                       */
/* qHead            pointer to the head of the queue      */
/* qTail            pointer to the tail of the queue      */
/* qItem            queue member structure                */
/*    next          pointer to next item on queue         */
/*    anItem        the item itself (must be proper type  */
/*                  to contain type of items on queue     */

typedef long member;       /* storing longs on this queue */
typedef struct item item;

struct item
{
   item    next;
   member  anItem;
};

item     quhead = NULL, *qtail = NULL;

                    /* Functions: */

/* add an item to queue */
void enqueue(item x)
{
   /* Allocate a new item structure */
   item    new;               /* pointer to new node */

   new = malloc(sizeof item);

   /* Place the item on the queue */
   new->item = x;
   new->next = NULL;

   If(empty())
      {
      /* Queue is empty, point the queue head and tail at
         the new item */
      qHead = new;
      qTail = new;
      }
   Else
      {
      /* Queue is not empty, insert the item and point
         everything to it */
      qTail->next = new;
      qTail = new;
   }
}

/* remove next item from queue */
void dequeue()
{             /* head is always next item   */
   qHead = qHead->next;

   If(qHead == NULL)
      /* queue is now empty */
      qTail = NULL;
}

/* return item at head of queue; don't remove */
member head()
{
   return (qHead->anItem);
}

/*  return true if the queue is empty, false otherwise */
int empty()
{
   return (qHead == NULL);
}