队列的基本操作-队列的链式存储结构（带图详细）
什么是队列？
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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
#include
//链式队列 链式结构+队列
//链式结构体 =单链表的基本单元：结点
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;
}
复制代码
现在的努力只为将来遇见更好的你！https://www.cnblogs.com/it1997/p/12071309.html