数据结构(链式队列)

链式存储的队列：链式队列

链式队列的组织形式与链表无异，只不过插入删除被约束在固定的两端。为了便于操作，通常也会 创建所谓管理结构体，用来存储队头指针、队尾指针、队列元素个数等信息：

从上图可以看到，链式队列主要控制队头和队尾，由于管理结构体中保存了当前队列元素个数 size，因此可以不必设计链表的头节点，初始化空队列时只需要让队头队尾指针同时指向空即可。 以下是队列链表节点设计和管理结构体设计的示例代码：

 typedef  int  DATA;
  // 链式队列节点
typedef struct _node
 {
    DATA        data;
    struct _node  *next;
 }NODE/*,*PNODE*/;
 // 链式队列管理结构体
typedef struct
 {
   NODE     *pHead; // 队头指针
   NODE     *pTail; // 队尾指针
   int       size ; // 队列当前元素个数
   int       num ;
 }LinkQueue;

• 链式队列的基本操作

分析

linkQueue.h

#ifndef  __LINKQUEUE_H
 #define  __LINKQUEUE_H
 typedef  int  DATA;
 // 链式队列节点
typedef struct _node
 {
    DATA        data;
    struct _node  *next;
 }NODE/*,*PNODE*/;
 // 链式队列管理结构体
typedef struct
 {
   NODE     *pHead; // 队头指针
   NODE     *pTail; // 队尾指针
   int       size ; // 队列当前元素个数
      int       num ;
 }LinkQueue;
 void LQ_init(LinkQueue *q,int sz);
 int  LQ_isfull(LinkQueue *q);
 int  LQ_isempty(LinkQueue *q);
 int  LQ_push(LinkQueue *q,DATA data);
 int  LQ_pop(LinkQueue *q,DATA *data);
 int LQ_free(LinkQueue *q);
 #endif

这段代码是一个链式队列的实现，其中定义了两个结构体，一个是节点结构体NODE，包含了数据和指向下一个节点的指针；另一个是队列管理结构体LinkQueue，包含了队头指针、队尾指针、队列当前元素个数和编号。

以下是对各个函数的解析：

LQ_init：初始化队列，将队头指针和队尾指针初始化为NULL，元素个数初始化为0，编号初始化为sz。
LQ_isfull：判断队列是否已满，如果队列当前元素个数等于编号，则队列已满，返回1；否则返回0。
LQ_isempty：判断队列是否为空，如果队头指针和队尾指针都为NULL，表示队列为空，返回1；否则返回0。
LQ_push：入队操作，将数据data插入到队尾，如果队列已满，返回0；否则返回1。
LQ_pop：出队操作，将队头的数据保存到data中，并删除队头节点，如果队列已空，返回0；否则返回1。
LQ_free：释放队列的空间，将所有节点依次删除。
整个代码通过上述函数对链式队列进行了初始化、判断队列是否为空或已满、入队、出队和释放空间的操作。

linkQueue.c

 #include "LinkQueue.h"
 #include <stdlib.h>
 void LQ_init(LinkQueue *q,int sz)
 {
    q -> pHead = q -> pTail = NULL;
    q -> size  = sz;
    q -> num   = 0;
 }
 int  LQ_isfull(LinkQueue *q)
 {
    return q -> num == q -> size;
 }
 int  LQ_isempty(LinkQueue *q)
 {
    return q -> num == 0;
 }
 int  LQ_push(LinkQueue *q,DATA data)
 {
    if(LQ_isfull(q))
       return -1;
    NODE* pNew = (NODE*)malloc(sizeof(NODE));
    if(!pNew)
        return -1;
    pNew -> data  = data;
    pNew -> next  = NULL;
    if(!(q -> pTail))
       q -> pHead = q -> pTail = pNew;
        else
    {       
       q -> pTail -> next  = pNew;
       q -> pTail = pNew;
    }
    q -> num ++;
    return 0;
 }
 int  LQ_pop(LinkQueue *q,DATA *data)
 {
    if(LQ_isempty(q))
       return -1;
     NODE* p = q -> pHead;
     *data  = p -> data;
     if(p == q -> pTail)
         q -> pHead = q -> pTail = NULL;
     else     
         q -> pHead = p -> next;
         
     free(p);
     q -> num --;
 
    return 0;
 }
 int LQ_free(LinkQueue *queue)
 {
    NODE* p = queue -> pHead, *q = NULL;
    while(p)
    {
        q  = p;
        p  = p -> next;
        free(q);
    }
    queue -> pHead = queue -> pTail = NULL;
    queue -> num   = 0;
    return 0;
 }

首先，LQ_init函数用于初始化队列，将队列的头指针、尾指针、大小和元素数量都初始化为合适的值。

LQ_isfull函数用于判断队列是否已满，如果队列元素数量与队列大小相等，则返回1表示队列已满，否则返回0表示队列未满。

LQ_isempty函数用于判断队列是否为空，如果队列元素数量为0，则返回1表示队列为空，否则返回0表示队列不为空。

LQ_push函数用于向队列中插入元素。首先判断队列是否已满，如果已满则返回-1表示插入失败。然后动态分配一个新节点，将数据存入新节点中。如果队列为空，则新节点即为头指针也为尾指针；如果队列不为空，则将新节点插入到尾节点的后面，并更新尾指针为新节点。最后增加队列的元素数量，并返回0表示插入成功。

LQ_pop函数用于从队列中取出元素。首先判断队列是否为空，如果为空则返回-1表示取出失败。然后将头指针指向节点的数据存入传入的data指针中，并更新头指针为下一个节点。如果取出后队列为空，则将尾指针也置为空。最后减少队列的元素数量，并释放原来的头节点。返回0表示取出成功。

LQ_free函数用于释放队列的内存。首先从头节点开始遍历队列，依次释放每个节点的内存。然后将头指针和尾指针都置为空，并将元素数量重置为0。返回0表示释放成功。

综上所述，这段代码实现了一个基本的链式队列，并提供了插入、取出和释放等基本操作函数。

linkQueue_main.c

#include "LinkQueue.h"
 #include <stdio.h>
 
 int main(void)
 {
    LinkQueue    queue;
    LQ_init(&queue,10);
    register  int i = 1;    
    for(; i <= 10 ; i++) 
       LQ_push(&queue, i);
    if( -1 == LQ_push(&queue,1024))
      fprintf(stderr,"满队,入队失败!\n");
    while(!LQ_isempty(&queue))
    {
        DATA   data;
        LQ_pop(&queue,&data);
        printf("%4d",data);
    }
    printf("\n");
    LQ_free(&queue);
    return 0; 
}

这段代码主要是测试LinkQueue.h中的链式队列的使用。 首先，在main函数中定义了一个LinkQueue类型的变量queue，并调用LQ_init函数对其进行初始化，设置队列的最大长度为10。

然后使用一个循环将1到10依次入队，使用LQ_push函数将数据入队。在入队前会判断队列是否已满，如果已满则会打印错误信息。

接下来使用一个循环将队列中的数据依次取出，使用LQ_pop函数将数据出队，并打印出来。

最后调用LQ_free函数释放队列中的内存，并返回0表示程序正常结束。

练习 4 」

构建一个链式队列，当用户输入数字时，将数字入队，当用户输入字母时，将队头元素出队。每次 操作队列之后，将队列中的元素显示出来。

解析： 链队列本质上就是一条链表，只不过其插入和删除被限制在两端。因此，按照基本的队列逻辑，封 装实现入队、出队等基本操作即可。 由于队列本质就是链表，因此实现链队列必然需要设计链接节点。另一方面，为了更好地管理链式 队列，一般需要提供一个管理结构体：

// 链队列的节点（实际上就是单链表节点）
struct node
 {
    int data;
    struct node *next;
 };
 // 链队列管理结构体
typedef struct
 {
    struct node *head; // 队列头元素指针
    struct node *tail; // 队列尾元素指针
    int size;          // 队列元素总数
}linkqueue;

参考代码：

 #include <stdio.h>
 #include <unistd.h>
 #include <stdlib.h>
 #include <stdbool.h>
 // 链队列的节点（实际上就是单链表节点）
struct node
 {
    int data;
    struct node *next;
 };
 // 链队列管理结构体
typedef struct
 {
    struct node *head; // 队列头元素指针
    struct node *tail; // 队列尾元素指针
    int size;          // 队列元素总数
}linkqueue;
 linkqueue * init_queue()
 {
      // 申请链队列管理结构体
    linkqueue *q = malloc(sizeof(linkqueue));
    if(q != NULL)
    {
        q->head = q->tail = NULL;
        q->size = 0;
    }
    return q;
 }
 bool is_empty(linkqueue *q)
 {
    return q->head == NULL;
 }
 struct node * out_queue(linkqueue *q)
 {
    if(is_empty(q))
        return NULL;
    struct node *tmp = q->head;
    q->head = q->head->next;
    tmp->next = NULL;
    // 若出队的元素是原队列中最后的元素，则更新队尾指针
    if(q->head == NULL)
        q->tail = NULL;
    return tmp;
 }
 void en_queue(linkqueue *q, struct node *new)
 {
    if(new == NULL)
        return;
    if(is_empty(q))
        q->head = q->tail = new;
    else
    {
        q->tail->next = new;
        q->tail = new;
    }
    q->size++;
 }
 void show(linkqueue *q)
     {
    if(is_empty(q))
        return;
    struct node *tmp;
    for(tmp=q->head; tmp!=NULL; tmp=tmp->next)
    {
        if(tmp==q->head)
            printf("【队头】");
        printf("%d", tmp->data);
        if(tmp->next == NULL)
            printf("【队尾】");
        printf("\t");
    }
    printf("\n");
 }
 struct node *new_node(int data)
 {
    struct node *new = malloc(sizeof(struct node));
    if(new != NULL)
    {
        new->data = data;
        new->next = NULL;
    }
    return new;
 }
 int main(void)
 {
    linkqueue *q = init_queue();
    int n, data;
    while(1)
    {
        // 如果输入数字，则入队
        if(scanf("%d", &n) == 1)
        {
            en_queue(q, new_node(n));
        }
        // 如果输入非数字，则出队并清空缓冲区
        else
        {
            while(getchar() != '\n');
             struct node *head = out_queue(q);
 if(!head)
 {
 printf("队列已空，出队失败.\n");
 continue;
 }
 printf("【%d】已出队\n", head->data);
 }
 show(q);
 }
 return 0;
 }