队列的链式储存结构

文章目录

队列的链式储存结构链队列的基本定义链队列的基本操作初始化队列求队列长度入队列操作出队列函数打印该队列 项目整体源代码：

链队列的基本定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的链式储存结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头节点，而队尾指针指向终端节点。

空队列时，front和rear都指向头节点。

链队列的基本操作

初始化队列

int Init_LinkQueue(LinkQueue *L) //初始化函数 { QNode *S; S = (QNode *)malloc(sizeof(Node)); //生成一个头节点，并为其分配空间 if (!S) { printf("初始化失败！\n"); return 0; } S->next = NULL; //将头节点的next域指向空 L->front = S; //将头指针指向头节点 L->rear = S; //将尾指针指向头节点 return 0; }

求队列长度

int Length_LinkQueue(LinkQueue *L) //计算队列长度 { int count = 0; QNode *S; S = L->front; //将头指针暂存在S while (L->front != L->rear) //循环，计算队列长度 { count++; L->front = L->front->next; } L->front = S; //将头指针返回到原位置 return count; }

入队列操作

int EnQueue(LinkQueue *L, elemtype e) //入队函数 { QNode *S; S = (QNode *)malloc(sizeof(Node)); //新增一个节点S，并为其分配空间 if (!S) { printf("插入元素失败！\n"); return 0; } S->data = e; //将e赋值给数据域 S->next = NULL; L->rear->next = S; //将新加入的节点S赋值给原先队尾节点的后继 L->rear = S; //让新加入的节点S设置为新的队尾节点 return 0; }

出队列函数

int DeQueue(LinkQueue *L, elemtype *e) //出队函数 { QNode *S; if (L->front == L->rear) { printf("当前队为空，无法删除元素！\n"); return 0; } S = L->front->next; //将欲删除的队头节点赋值给S *e = S->data; //通过e返回要删除的元素值 L->front->next = S->next; //将要删除节点的下一个节点赋值给头节点的后继 if (L->rear == S) //如果删除的是尾节点 L->rear = L->front; //则将尾指针指向和头指针一样的头节点，代表队为空 free(S); //释放要删除的节点 return 0; }

打印该队列

void Show_LinkQueue(LinkQueue *L) //打印队列函数 { if (L->front == L->rear) { printf("队列为空！\n"); return; } QNode *S; S = L->front; //将头指针暂存在S L->front = L->front->next; //先将头指针指向头结点的后继节点，即第一个节点 printf("当前队列元素为："); while (L->front) //当没有到尾节点，就一直循环 { printf("%d ", L->front->data); L->front = L->front->next; } printf("\n"); L->front = S; //将头指针回到原位置 }

到此，队列链式储存的基本操作就已经完成了，下面附上源码

项目整体源代码：

#include<stdio.h> #include<stdlib.h> typedef int elemtype; typedef struct Node //节点结构 { elemtype data; struct Node *next; }QNode,*QueuePtr; typedef struct { QueuePtr front, rear; //队头，队尾指针 }LinkQueue; int Init_LinkQueue(LinkQueue *L) //初始化函数 { QNode *S; S = (QNode *)malloc(sizeof(Node)); //生成一个头节点，并为其分配空间 if (!S) { printf("初始化失败！\n"); return 0; } S->next = NULL; //将头节点的next域指向空 L->front = S; //将头指针指向头节点 L->rear = S; //将尾指针指向头节点 return 0; } int EnQueue(LinkQueue *L, elemtype e) //入队函数 { QNode *S; S = (QNode *)malloc(sizeof(Node)); //新增一个节点S，并为其分配空间 if (!S) { printf("插入元素失败！\n"); return 0; } S->data = e; //将e赋值给数据域 S->next = NULL; L->rear->next = S; //将新加入的节点S赋值给原先队尾节点的后继 L->rear = S; //让新加入的节点S设置为新的队尾节点 return 0; } int DeQueue(LinkQueue *L, elemtype *e) //出队函数 { QNode *S; if (L->front == L->rear) { printf("当前队为空，无法删除元素！\n"); return 0; } S = L->front->next; //将欲删除的队头节点赋值给S *e = S->data; //通过e返回要删除的元素值 L->front->next = S->next; //将要删除节点的下一个节点赋值给头节点的后继 if (L->rear == S) //如果删除的是尾节点 L->rear = L->front; //则将尾指针指向和头指针一样的头节点，代表队为空 free(S); //释放要删除的节点 return 0; } int Length_LinkQueue(LinkQueue *L) //计算队列长度 { int count = 0; QNode *S; S = L->front; //将头指针暂存在S while (L->front != L->rear) //循环，计算队列长度 { count++; L->front = L->front->next; } L->front = S; //将头指针返回到原位置 return count; } void Show_LinkQueue(LinkQueue *L) //打印队列函数 { if (L->front == L->rear) { printf("队列为空！\n"); return; } QNode *S; S = L->front; //将头指针暂存在S L->front = L->front->next; //先将头指针指向头结点的后继节点，即第一个节点 printf("当前队列元素为："); while (L->front) //当没有到尾节点，就一直循环 { printf("%d ", L->front->data); L->front = L->front->next; } printf("\n"); L->front = S; //将头指针回到原位置 } int main() { LinkQueue L; elemtype m; Init_LinkQueue(&L); Show_LinkQueue(&L); printf("队列的长度为%d\n", Length_LinkQueue(&L)); EnQueue(&L, 5); EnQueue(&L, 3); EnQueue(&L, 32); EnQueue(&L, 65); Show_LinkQueue(&L); printf("队列的长度为%d\n", Length_LinkQueue(&L)); DeQueue(&L,&m ); printf("被删除元素为：%d\n", m); DeQueue(&L, &m); printf("被删除元素为：%d\n", m); Show_LinkQueue(&L); printf("队列的长度为%d\n", Length_LinkQueue(&L)); system("pause"); return 0; }