/*************************************************
  filename: queue.c
  author:   dan brown
  email:    snowman@cs.cornell.edu
  date:     25 august 1997

  This code implements a queue data structure as a linked list.  
  *************************************************/

#include "queue.h"

/* initialize the fields in an empty queue */
void QInitialize (Queue *pQ)
{
  pQ -> nSize = 0;
  pQ -> pHead = NULL;
  pQ -> pTail = NULL;
}

/* test if a queue is empty */
int QEmpty (Queue Q)
{
  return (Q.nSize == 0);
}

/* remove front element from the queue */
int QExtract (Queue* pQ)
{
  QueueNode* pTmp;  /* so we can preserve the front after the queue
		       has moved off of it */
  int nReturn;      /* value at the front of the queue */

  if (pQ->nSize == 0)
    {
      /* if this were C++, this would raise an exception */
      printf ("Error: extracting null queue!\n");
      return 0;
    }
  (pQ -> nSize)--;
  pTmp = pQ -> pHead;
  pQ -> pHead = pTmp -> pNext;

  /* if the queue is now empty, the tail should point to nothing now */
  if (pQ -> nSize == 0)
    pQ -> pTail = NULL;
  
  nReturn = pTmp -> nData;
  free (pTmp);
  return nReturn;
}

/* Insert a new element into the queue.  */
void QInsert (Queue* pQ, int nNewData)
{
  QueueNode* pNew;  /* new node for the queue */
  
  pNew = (QueueNode*) malloc (sizeof (QueueNode));
  if (!pNew)
    {
      printf ("Not enough memory!\n");
      exit (-1);
    }
  pNew -> nData = nNewData;
  pNew -> pNext = NULL;

  /* point the old queue to this new node.  */
  /* If the old queue was empty, this new node is the head and the
     tail. */
  if (pQ -> nSize == 0)
    pQ -> pHead = pQ -> pTail = pNew;
  else
    {
      pQ -> pTail -> pNext = pNew;
      pQ -> pTail = pNew;
    }
  /* increment the size counter */
  (pQ->nSize)++;
}

/* Throw out all memory left in the queue.  This works by just
   repeatedly extracting the front element until the queue is empty. */
void QDestroy (Queue *pQ)
{
  while (pQ -> nSize > 0)
    QExtract (pQ);
}