链式队列的实现

链式队列的实现，基于企业级链表

队列先进先出，这是他的一个特征，我们还是老规矩用企业级链表和一个队列结垢体把他封装一下

具体的思路就是：

1. 设置一个Node结构体来存储每个队列节点的地址，他就相当于一个钩子，把所有的链表节点连接起来

   struct Node
   {
       struct Node *next;
   };

2. 设置一个队列节点，存储队列的基本信息，包括长度，上一个节点和下一个节点的地址

   typedef struct LinkQueue
   {
       int len;
       struct Node tail;
       struct Node head;
   }LinkQueue;

3. 包装函数，init，push，pop，isempty

   #include<stdio.h>
   #include <stdlib.h>
   //队列结构体的连接节点
   struct Node
   {
       struct Node *next;
   };
   //队列的对应结构体，来存储队列元素的基本信息，struct Node *tail，是因为
   struct LQueue
   {
       int len;
       struct Node *tail;
       struct Node head;
   }LQueue;
   typedef  void *  LinkQueue;
   struct LinkQueue * Init_Queue()
   {
       struct LQueue * queue=malloc(sizeof(struct LQueue));
       if(NULL==queue)
       {
           return NULL;
       }
        queue->head.next=NULL;
        queue->len=0;
        queue->tail=&(queue->head);//刚开始没有数据，所以首尾节点是重和的
       return queue;
   };
   void Push_Queue(LinkQueue *queue,void * data)
   {
   
       if(queue==NULL || NULL==data)
       {
           return;
       }
       //把void *转化为正常的结构体类型，这样方便获取里面数据
       struct LQueue * Myqueue=(struct LQueue *)queue;
       //把用户数据的前四个字节转化为节点类型，也就是连接每一个队列结构体的钩子
       //所以后面的测试时，Person结构体前面也该加一个 struct NOde node;
       struct Node * Mydata=(struct Node *)data;
       /*************************************************************/
       //加入尾节点的数据，但是这个尾节点既是节点也是数据，所以后面会需要更新尾节点
       Myqueue->tail->next=data;
       //尾节点的next为空
       Mydata->next=NULL;
       //更新尾节点的Node，相当于给尾节点加入了一个Node
       Myqueue->tail=data;
       /************************************************************/
       Myqueue->len++;
   }
   void Pop_Queue(LinkQueue *queue)
   {
       if(queue==NULL)
       {
           return ;
       }
      struct LQueue *Myqueue=(struct LQueue *)queue;
      if(Myqueue->len==0)
      {
          return;
      }
      if(Myqueue->len==1)
      {
           Myqueue->head.next=NULL;
           Myqueue->tail=&(Myqueue->head);
           Myqueue->len--;
           return;//bug找了半天，这里自己少了一个return，导致，len等于1时，被执行了两次出队操作
   
      }
       //存储队列第一个节点的数据
      struct Node * FirstNode=Myqueue->head.next;
       //执行出队的操作，把头节点的next指向第二个节点及就是出队
      Myqueue->head.next=FirstNode->next;
   
       --Myqueue->len;
   
   
   }
   void * Top_LinkQueue(LinkQueue * queue)
   {
       if(queue==NULL)
       {
           return NULL;
       }
       struct LQueue *Myqueue=(struct LQueue *)queue;
       if(Myqueue->len<=0)
       {
           return NULL;
       }
       return Myqueue->head.next;
   
   };
   void  * Tail_LinkQueue(LinkQueue * queue)
   {
       if(queue==NULL)
       {
           return NULL;
       }
       struct LQueue *Myqueue=(struct LQueue *)queue;
       if(Myqueue->len<=0)
       {
           return NULL;
       }
       return Myqueue->tail;
   
   };
   int Size_Queue(struct LinkQueue *queue)
   {
       if(queue==NULL)
       {
           return -1;
       }
       struct LQueue * Myqueue=(struct LQueue *)queue;
       return Myqueue->len;
   }
   int  Isempty_LinkQueue(LinkQueue *queue)
   {
       if(queue==NULL)
       {
           return 0  ;
       }
       struct LQueue *Myqueue=( struct LQueue *)queue;
       if(Myqueue->len<=0)
       {
           return 1;
       }
       else
       {
   
           return 0;
       }
   
   }
   void Destroy_Queue(LinkQueue * queue)
   {
   
       if(queue==NULL)
       {
           return ;
       }
       struct LQueue * Myqueue=(struct LQueue *)queue;
       Myqueue->head.next=NULL;
       Myqueue->tail=NULL;
       Myqueue->len=0;
       free(queue);
       Myqueue=NULL;
   }
   
   struct Person
   {
       struct Node node;//是用来存储下一个队列节点的信息的，刚开始没有加这个，
       char name[64];
       int age;
   
   };
   void test()
   {
   
   	//初始化栈
   	struct LQueue*  queue = Init_Queue();
   
   
   	//创建数据
   	struct Person p1 = { NULL,"aaa", 10 };
   	struct Person p2 = { NULL,"bbb", 20 };
   	struct Person p3 = { NULL,"ccc", 30 };
   	struct Person p4 = { NULL,"ddd", 40 };
   	struct Person p5 = { NULL,"eee", 50 };
   	struct Person p6 = { NULL,"fff", 60 };
   	Push_Queue(queue,&p1);
   	Push_Queue(queue,&p2);
   	Push_Queue(queue,&p3);
   	Push_Queue(queue,&p4);
       Push_Queue(queue,&p5);
       Push_Queue(queue,&p6);
     	while(Size_Queue(queue)>0)
       {
           struct Person *p=(struct Person *)Top_LinkQueue(queue);
           printf("name: %s    age: %d\n",(p->name),p->age);
           Pop_Queue(queue);
           printf("size=%d\n",Size_Queue(queue));
       }
        printf("size=%d\n",Size_Queue(queue));
        Destroy_Queue(queue);
   
   }
   int main(void)
   {
       test();
       return 0;
   }
   

总结：

1. 初始化队列时应该进行的操作包括，mallco分配空间，设置首尾节点的值，以及队列长度的值。初始化时首尾节点为同一个

   head.next=NULL;
   tail->next=&(queue->head);

2. 队列的入队操作，*用户输入数据为void 。

   第一步：先转化为节点指针类型

   struct  Node * mydata=data;
   

   第二步：分别把struct Node * mydata里面的数据段和节点段，用于更新队列尾节点

   struct  Node * mydata=data;
   //队列的尾节点节点，数据更新
   queue->tail->next=data;
   //新的尾节点的next为NULL
   mydata->next=NULL;
   //把插入的这个节点当作尾节点
   queue->tail=data;
   queue->len++;

3. 队列的出队操作，这里有几个地方要注意，队列的出队其实是根据他的长度不同执行的操作是不一样的

   if(queue->len==1)
   {
   	queue->head.next=NULL;
   	//队列中只有一个元素是，出队之后就是和初始化时一样了，首尾节点重回
   	queue->tail=&(queue->head)
       queue->len--;
   }
   if(queue->len>1)
   {
       //存储第一个节点
   	struct Node * myfirstnode=queue->head.next;
       //使得头节点指向第二个节点，就是出队操作了
       queue->head.next=myfirstnode->next;
       queue->len--;
   }