#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkQueue.h"

/*------------------------------------------------------------
操作目的： 初始化隊(duì)列
初始條件： 無
操作結(jié)果： 構(gòu)造一個(gè)空的隊(duì)列
函數(shù)參數(shù)：
  LinkQueue *Q 待初始化的隊(duì)列
返回值：
  bool   操作是否成功
------------------------------------------------------------*/
bool InitQueue(LinkQueue *Q)
{
 Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
 if(!Q->front)
  return false;
 Q->front->next = NULL;
 return true;
}

/*------------------------------------------------------------
操作目的： 銷毀隊(duì)列
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 銷毀隊(duì)列Q
函數(shù)參數(shù)：
  LinkQueue *Q 待銷毀的隊(duì)列
返回值：
  無
------------------------------------------------------------*/
void DestroyQueue(LinkQueue *Q)
{
 while(Q->front)
 {
  Q->rear = Q->front->next;
  free(Q->front);
  Q->front = Q->rear;
 }
}

/*------------------------------------------------------------
操作目的： 判斷隊(duì)列是否為空
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 若Q為空隊(duì)列，則返回true，否則返回false
函數(shù)參數(shù)：
  LinkQueue Q  待判斷的隊(duì)列
返回值：
  bool   是否為空
------------------------------------------------------------*/
bool QueueEmpty(LinkQueue Q)
{
 if(Q.front == Q.rear)
  return true;
 return false;
}

/*------------------------------------------------------------
操作目的： 得到隊(duì)列的長度
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 返回Q中數(shù)據(jù)元素的個(gè)數(shù)
函數(shù)參數(shù)：
  LinkQueue Q  隊(duì)列Q
返回值：
  int    數(shù)據(jù)元素的個(gè)數(shù)
------------------------------------------------------------*/
int QueueLength(LinkQueue Q)
{
 ElemType count=0;
 QueuePtr p = Q.front->next;
 while(p->next != NULL)
 {
  ++count;
  p = p->next;
 }
 return count;
}

/*------------------------------------------------------------
操作目的： 得到隊(duì)列首元素
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 用e返回隊(duì)列首元素
函數(shù)參數(shù)：
  LinkQueue Q  隊(duì)列Q
  ElemType *e  隊(duì)列首元素的值
返回值：
  bool   操作是否成功
------------------------------------------------------------*/
bool GetHead(LinkQueue Q, ElemType *e)
{
 if(QueueEmpty(Q) == false)
 {
  e = &Q.front->next->data;
  return true;
 }
 return false;
}

/*------------------------------------------------------------
操作目的： 遍歷隊(duì)列
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 依次對(duì)Q的每個(gè)元素調(diào)用函數(shù)fp
函數(shù)參數(shù)：
  LinkQueue Q  隊(duì)列Q
  void (*fp)() 訪問每個(gè)數(shù)據(jù)元素的函數(shù)指針
返回值：
  無
------------------------------------------------------------*/
void QueueTraverse(LinkQueue Q, void (*fp)(ElemType))
{
 QueuePtr p = Q.front->next;
 while(p->next != NULL)
 {
  visit(p->data);
  p = p->next;
 }
}

/*------------------------------------------------------------
操作目的： 清空隊(duì)列
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 將隊(duì)列清空
函數(shù)參數(shù)：
  LinkQueue *Q 隊(duì)列Q
返回值：
  無
------------------------------------------------------------*/
void ClearQueue(LinkQueue *Q)
{
 ElemType x=0;
 while(Q->front != Q->rear)
 {
  DeQueue(Q,&x);
  Q->front = Q->front->next;
 }
}

/*------------------------------------------------------------
操作目的： 在隊(duì)列末尾插入元素e
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 插入元素e作為隊(duì)列新的尾結(jié)點(diǎn)
函數(shù)參數(shù)：
  LinkQueue *Q  隊(duì)列Q
  ElemType e  待插入的數(shù)據(jù)元素
返回值：
  bool   操作是否成功
------------------------------------------------------------*/
bool EnQueue(LinkQueue *Q, ElemType e)
{
 QueuePtr p;
 p = (QueuePtr)malloc(sizeof(QNode));
 if(!p)
  return false;
 p->data = e;
 p->next = NULL;
 Q->rear->next = p;
 Q->rear = p;
 return true;
}

/*------------------------------------------------------------
操作目的： 刪除鏈?zhǔn)疥?duì)列的頭結(jié)點(diǎn)
初始條件： 隊(duì)列Q已存在
操作結(jié)果： 刪除鏈?zhǔn)疥?duì)列的頭結(jié)點(diǎn)
函數(shù)參數(shù)：
  LinkQueue *Q  隊(duì)列Q
  ElemType *e  被刪除的數(shù)據(jù)元素
返回值：
  bool   操作是否成功
------------------------------------------------------------*/
bool DeQueue(LinkQueue *Q, ElemType *e)
{
 QueuePtr p;
 if(Q->front == Q->rear)
  return false;
 p = Q->front->next;
 *e = p->data;
 Q->front->next = p->next;
 if(Q->rear == p)
  Q->rear = Q->front;
 free(p);
 return true;
}