快速搞懂数据结构之链式队列_链式队列,输入数字入队,输入字符出队

什么是链式队列？

本篇仅用于记录自己所学知识及应用，代码仍可优化，仅供参考，如果发现有错误的地方，尽管留言于我，谢谢!

队列有两种存储形式：顺序存储和链式存储。
采用顺序队列存储的队列称为顺序队列。
顺序队列采用数组存储队列中的元素，使用两个指针尾指针(rear)和头指针（front）分别指向队列的队头和队尾。使用顺序队列由于在操作时会出现“假溢出现象”，所以可以使用顺序循环队列合理的使用队列空间。
顺序队列的实现可以参考 快速搞懂数据结构之顺序队列
采用链式存储的队列称为链式队列。
链式队列使用链表来实现，链表中的数据域用来存放队列中的元素，指针域用来存放队列中下一个元素的地址，同时使用队头指针和队尾指针指向队列的第一个元素和最后一个元素。
插入操作在队尾进行，删除操作在队头进行，由队头指针和队尾指针控制队列的操作。
链式队列的出队和入队的操作可参考下图：

创建链式队列必须的节点

// 链式队列存储的元素类型，默认是int
typedef  int  data_t;  
   // 链式队列节点
typedef  struct  node_t
{
      data_t data ;		
   struct node_t   *next; 	
 } linknode_t,  *linklist_t; 
  // 链式队列的管理结构体                
 typedef  struct
  {
     linklist_t  front,  rear; 
  } linkqueue_t; 	
1
2
3
4
5
6
7
8
9
10
11
12
13

关键操作函数

链式队列存储示意图：

创建空队列 ：

空队列示意图：

linkqueue_t  *CreateQueue()
{
    
      linkqueue_t  *lq  =  (linkqueue_t  *)malloc(sizeof(linkqueue_t));
      lq->front = lq->rear = (linklist_t)malloc(sizeof(linknode_t));
      lq->front->next = NULL ;	  /*置空队*/
          return  lq;     /*返回队列指针*/
}
1
2
3
4
5
6
7
8

判断队列空 ：

int   EmptyQueue(linkqueue_t  *lq)  {
    
   return ( lq->front  = =  lq->rear) ;
} 
1
2
3
4

入队

void  EnQueue (linkqueue_t *lq, data_t x)
{
   
      lq->rear->next = (linklist_t)malloc(sizeof(linknode_t)
1
2
3