链表实现队列

这次写的还算正规，稍微压缩了一下代码，但是不影响阅读

画个图帮助理解：

F->0->0->0<-R

第一个0不存数据 

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<malloc.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      typedef int Elementype;//数据类型
     
    
   

    

     

    
    

     

      //节点结构
     
    
   

    

     

    
    

     

      typedef struct Node{
     
    
   

    

     

    
    

     

       Elementype Element;//数据域
     
    
   

    

     

    
    

     
 struct Node * Next;
     
    
   

    

     

    
    

     

      }NODE,*PNODE;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // 定义队列结构体
     
    
   

    

     

    
    

     

      typedef struct QNode {
     
    
   

    

     

    
    

     

       PNODE Front;//队头
     
    
   

    

     

    
    

     

       PNODE Rear;//队尾
     
    
   

    

     

    
    

     

      } Queue, *PQueue;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void init(PQueue queue)//初始化
     
    
   

    

     

    
    

     

      {//头尾指向同一内存空间//头结点，不存数据
     
    
   

    

     

    
    

     
 queue->Front = queue->Rear = (PNODE)malloc(sizeof(NODE));
     
    
   

    

     

    
    

     
 queue->Front->Next = NULL;//头结点指针为空
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int isEmpty(PQueue queue)//判空·
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(queue->Front == queue->Rear)return 1;
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void insert(PQueue queue,Elementype data)//入队
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       PNODE P = (PNODE)malloc(sizeof(NODE));//初始化
     
    
   

    

     

    
    

     

       P->Element = data;
     
    
   

    

     

    
    

     

       P->Next = NULL;
     
    
   

    

     

    
    

     
 queue->Rear->Next = P;//入队
     
    
   

    

     

    
    

     
 queue->Rear = P;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void delete(PQueue queue,int * val)//出队，用val返回值
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(isEmpty(queue))printf("队空");
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       PNODE  P = queue->Front->Next;//前一元素
     
    
   

    

     

    
    

     

       *val = P->Element;//记录值
     
    
   

    

     

    
    

     
 queue->Front->Next = P->Next;//出队
     
    
   

    

     

    
    

     
 //注意一定要加上判断，手动模拟一下就明白了
     
    
   

    

     

    
    

     
 if(P==queue->Rear)queue->Rear = queue->Front;
     
    
   

    

     

    
    

     
 free(P);//注意释放
     
    
   

    

     

    
    

     

       P = NULL;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void destroy(PQueue queue)//释放
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //从头开始删
     
    
   

    

     

    
    

     
 while(queue->Front != NULL)//起临时指针作用，无需再用别的空间
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 queue->Rear = queue->Front->Next;
     
    
   

    

     

    
    

     
 free(queue->Front);
     
    
   

    

     

    
    

     
 queue->Front = queue->Rear;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //测试
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i;
     
    
   

    

     

    
    

     
 int e;
     
    
   

    

     

    
    

     

       Queue a;
     
    
   

    

     

    
    

     

       PQueue queue=&a;
     
    
   

    

     

    
    

     

       init(queue);
     
    
   

    

     

    
    

     
 for(i=0;i<10;i++)
     
    
   

    

     

    
    

     

       insert(queue,i);
     
    
   

    

     

    
    

     
 while(!isEmpty(queue))//遍历
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 delete(queue,&e);
     
    
   

    

     

    
    

     
 printf("%d ",e);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(isEmpty(queue))printf("1\n");
     
    
   

    

     

    
    

     
 delete(queue,&e);
     
    
   

    

     

    
    

     

       destroy(queue);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82863168