在前面两篇博客中,我分别使用了静态数组和动态数组来模拟循环队列。但是线性表中和队列神似的莫过于链表了。我在前面也使用了大量的篇幅来讲述了链表的各种操作。我们使用一种比较特殊的链表——非循环双向链表来实现队列。首先这里的说明的是构建的是普通的队列,而不是循环队列。当我们使用数组的时候创建循环队列是为了节省存储空间,而来到链表中时,每一个节点都是动态申请和释放的,不会造成空间的浪费,所以不需要采用循环队列了。第二,大家在很多书上看到的是使用单链表实现队列,我这里将会使用带头结点尾结点的非循环双链表实现,虽然多维护了两个节点和指针域,但是在链表头尾进行插入删除的时候不需要遍历链表了,队列操作变得非常的方便。真正实现了只在头尾操作。代码上传至https://github.com/chenyufeng1991/Queue_LinkedList
  核心代码如下:
  (1)初始化队列
  //初始化带头结点和尾结点的非循环双向链表
  void InitialQueue(Queue **pHead,Queue **pTail){
  *pHead = (Queue *)malloc(sizeof(Queue));
  *pTail = (Queue *)malloc(sizeof(Queue));
  if (*pHead == NULL || *pTail == NULL) {
  printf("%s函数执行,内存分配失败,初始化双链表失败 ",__FUNCTION__);
  }else{
  //这个里面是关键,也是判空的重要条件
  (*pHead)->next = NULL;
  (*pTail)->prior = NULL;
  //链表为空的时候把头结点和尾结点连起来
  (*pHead)->prior = *pTail;
  (*pTail)->next = *pHead;
  printf("%s函数执行,带头结点和尾节点的双向非循环链表初始化成功 ",__FUNCTION__);
  }
  }
  (2)入队,在尾结点插入元素
  //入队,也是在链表的尾部插入节点
  void EnQueue(Queue *head,Queue *tail,int x){
  Queue *pInsert;
  pInsert = (Queue *)malloc(sizeof(Queue));
  memset(pInsert, 0, sizeof(Queue));
  pInsert->next = NULL;
  pInsert->prior = NULL;
  pInsert->element = x;
  tail->next->prior = pInsert;
  pInsert->next = tail->next;
  tail->next = pInsert;
  pInsert->prior = tail;
  }
  (3)出队,在头结点处删除节点
  //出队,在队列头部删除元素
  void DeQueue(Queue *head,Queue *tail){
  if (IsEmpty(head,tail)) {
  printf("队列为空,出队列失败 ");
  }else{
  Queue *pFreeNode;
  pFreeNode = head->prior;
  head->prior->prior->next = head;
  head->prior = head->prior->prior;
  free(pFreeNode);
  pFreeNode = NULL;
  }
  }
  (4)打印所有节点
  //打印出从队列头部到尾部的所有元素
  void PrintQueue(Queue *head,Queue *tail){
  Queue *pMove;
  pMove = head->prior;
  printf("当前队列中的元素为(从头部开始):");
  while (pMove != tail) {
  printf("%d ",pMove->element);
  pMove = pMove->prior;
  }
  printf(" ");
  }
  (5)判断队列是否为空
  //判断队列是否为空,为空返回1,否则返回0
  int IsEmpty(Queue *head,Queue *tail){
  if (head->prior == tail) {
  return 1;
  }
  return 0;
  }
  (6)测试代码
  int main(int argc, const char * argv[]) {
  Queue *pHead;//头结点
  Queue *pTail;//尾结点
  InitialQueue(&pHead, &pTail);
  EnQueue(pHead, pTail, 2);EnQueue(pHead, pTail, 1);
  EnQueue(pHead, pTail, 9);EnQueue(pHead, pTail, 3);EnQueue(pHead, pTail, 4);
  PrintQueue(pHead, pTail);
  DeQueue(pHead,pTail);DeQueue(pHead,pTail);DeQueue(pHead,pTail);
  PrintQueue(pHead, pTail);
  return 0;
  }