队列的基本操作-队列的链式存储结构
什么是队列？
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
链式队列是用单链表的形式来表示队列，但是要符合队列“尾进头出”的规则
链式队列的构建：
链式队列=单链表+队列。
如下代码是对一个队列的链式存储的定义：首先定义一个构成单链表基本单元的结点，然后定义由指向结点的头指针、指向结点的尾指针和表示队列长度的变量组成的队列
//链式队列 链式结构+队列 //链式结构体 =单链表的基本单元：结点 struct Node{ int data;//数据域 struct Node* next; //指针域 }; //队列结构体=头指针+尾指针+队列大小 struct Queue{ struct Node* front;//指向结点的头指针 struct Node* rear;//指向结点的尾指针 int queueSize; //队列大小/长度 };
创建结点：
队列是由一个一个结点通过指针链接起来的
//创建结点 struct Node* createNode(int data){ struct Node* newNode=(struct Node*)malloc(sizeof(struct Node)); newNode->next=NULL; newNode->data=data; return newNode; };
队列的初始化：
首先使用malloc函数为队列分配一块内存，初始状态队列的头指针和尾指针在一起都为空（不带头结点），然后设置队列的大小为0。这样队列的初始化操作就完成了。
//队列初始化 struct Queue* createQueue(){ struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配内存空间 queue->front=queue->rear=NULL;//头指针和尾指针在一起为空 queue->queueSize=0;//队列大小为0 return queue; }
入队操作：
准备工作：首先创建入队函数push()传入两个参数，一个是需要插入那个队列另一个是需要插入的数据。然后调用createNode()函数创建一个新的结点，保存插入的数据。
准备工作完成后：先判断队列是否是空队列，如果为空队列直接将front和rear指针指向这个新建结点即可，若不为空，则将尾指针的下一个位置指向新建结点，然后再将尾指针修改为这个新建结点。（这个地方我个人感觉比较难懂，我的理解是 先告诉这个新建结点在哪里，然后在移动rear指针到新建结点把他设为队尾）。
最后别忘记queueSize自增，表示队列长度的增加。
void push(struct Queue* queue,int data){ struct Node* newNode=createNode(data); if(queue->queueSize==0) queue->front=newNode; else queue->rear->next=newNode; queue->rear=newNode; queue->queueSize++; }
获取对头元素：
首先判断队列queueSize是否为0如果为0说明队列为空，如果不为空直接返回队列头指针的data值。
//获取对头元素 int queryFront(struct Queue* queue) { if(queue->queueSize==0){ printf("队列为空无法获取对头元素"); printf("\n"); return -1; } return queue->front->data; }
判断队列是否为空：
代码很简单就不一一解释了。
//判断队列是否为空 int empty(struct Queue* queue){ if(queue->queueSize==0) return 0; else return 1; }
出队操作：
新建头结点指针指向队列front指针所指结点的下一个位置（因为出队操作是在对头进行的），然后释放原来的队头结点，最后设置这个新的头结点为队头。最后队列的大小减1.
//出队操作 void pop (struct Queue* queue){ if(queue->queueSize==0){ printf("队列为空不能出队"); exit(0); }else{ struct Node* newFrontNode=queue->front->next; free(queue->front); queue->front=newFrontNode; queue->queueSize--; } }
最后附上完整代码：
#include <stdio.h> #include <stdlib.h> //链式队列 链式结构+队列 //链式结构体 =单链表的基本单元：结点 struct Node{ int data;//数据域 struct Node* next; //指针域 }; //队列结构体=头指针+尾指针+队列大小 struct Queue{ struct Node* front;//指向结点的头指针 struct Node* rear;//指向结点的尾指针 int queueSize; //队列大小/长度 }; //创建结点 struct Node* createNode(int data){ struct Node* newNode=(struct Node*)malloc(sizeof(struct Node)); newNode->next=NULL; newNode->data=data; return newNode; }; //队列初始化 struct Queue* createQueue(){ struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配内存空间 queue->front=queue->rear=NULL;//头指针和尾指针在一起为空 queue->queueSize=0;//队列大小为0 return queue; } //入队 void push(struct Queue* queue,int data){ struct Node* newNode=createNode(data); if(queue->queueSize==0) queue->front=newNode; else queue->rear->next=newNode; queue->rear=newNode; queue->queueSize++; } //获取对头元素 int queryFront(struct Queue* queue) { if(queue->queueSize==0){ printf("队列为空无法获取对头元素"); printf("\n"); return -1; } return queue->front->data; } //判断队列是否为空 int empty(struct Queue* queue){ if(queue->queueSize==0) return 0; else return 1; } //出队操作 void pop (struct Queue* queue){ if(queue->queueSize==0){ printf("队列为空不能出队"); exit(0); }else{ struct Node* newFrontNode=queue->front->next; free(queue->front); queue->front=newFrontNode; queue->queueSize--; } } int main(){ struct Queue* myQueue=createQueue(); push(myQueue,1); push(myQueue,2); push(myQueue,3); while(empty(myQueue)){ printf("%d\t",queryFront(myQueue)); pop(myQueue); } printf("\n"); system("pause"); return 0; }