概述
在日常生活中,先进先出似乎更加符合我们的日常认知。
排队的人群中,队首的人总是先离开,而队尾的人总是后离开。
1.队列的基本原理和操作
我们知道队列也是一种线性表,而今天我们就用非顺序储存结构(链表)来实现它。
首先我们先明确队列的基本操作原理:因为同时涉及到队首和队尾的操作,所以仅用一个头指针是不好解决问题的,所以在这里我们采用双指针的方式(即分别用两个指针*front、*rear指向队首和队尾)。然后再考虑一下队列中还要有什么元素?当然是队列的长度size了。接着是节点的常规定义:
#include <stdio.h>
#include <stdlib.h>
#define eletype int
typedef struct Node {
eletype data;
struct Node* next;
} Node;
typedef struct Queue {
Node *front; //定义两个指针,*front指向队首,*rear指向队尾
Node *rear;
int size;
} Queue;
2.队列的创建
队列的创建需要将先前出现的变量进行初始化:
void QueueCreat (Queue *q) {
q->front=NULL;
q->rear=NULL;
q->size=0;
}
3.队列的销毁
销毁只需要从队首开始逐步将队列的空间释放掉,注意每释放一次就要将队首指针更新一次:
void QueueDestroy (Queue *q) {
while(q->front){
Node* temp=q->front;
q->front=q->front->next; //然后更新队首指针,直到循环条件中q->front==NULL
free(temp); //释放队首指针的空间
}
q->rear=NULL;
q->size=0;
}
4.入队
入队操作需要Queue *q、eletype element作为传入的参数。而我们要做的就是将element存入一个节点的数据域, 再将该节点更新为新的队首节点:
void QueuePush (Queue *q,eletype element) {
Node* new_Node=(Node*)malloc(sizeof(Node));
new_Node->data=element;
new_Node->next=NULL;
if(q->rear==NULL){
q->front=q->rear=new_Node; //判断是否为空队列,若是,队首队尾指针都指向新节点即可
} else {
new_Node->next=q->rear; //若否,则将新节点链接到q->rear,并更新队尾节点
q->rear=new_Node;
}
q->size++;
}
5.出队
删除元素是在队首进行的,需要将队首空间释放,且更新队首指针(注意要判断队列是否为空,并打印相关提示信息),最后将队首元素带回:
eletype QueuePop (Queue *q) {
if(q->front==NULL){
printf("Queue is empty!\n");
exit(1);
}
eletype result=q->front->data;
Node *temp=q->front;
q->front=q->front->next; //更新队首指针
free(temp); //定义一个*temp来接收q->front,并将其释放掉
q->size--;
return result;
}
6.获取队首元素
eletype QueueTop (Queue *q) {
return q->front->data;
}
7.获取队列的长度
int QueueGetsize (Queue *q) {
return q->size;
}
8.完整源码
#include <stdio.h>
#include <stdlib.h>
#define eletype int
typedef struct Node {
eletype data;
struct Node* next;
} Node;
typedef struct {
Node *front; //定义两个指针,*front指向队首,*rear指向队尾
Node *rear;
int size;
} Queue;
void QueueCreat (Queue *q) {
q->front=NULL;
q->rear=NULL;
q->size=0;
}
void QueueDestroy (Queue *q) {
while(q->front){
Node* temp=q->front;
q->front=q->front->next; //然后更新队首指针,直到循环条件中q->front==NULL
free(temp); //释放队首指针的空间
}
q->rear=NULL;
q->size=0;
}
void QueuePush (Queue *q,eletype element) {
Node* new_Node=(Node*)malloc(sizeof(Node));
new_Node->data=element;
new_Node->next=NULL;
if(q->rear==NULL){
q->front=q->rear=new_Node; //判断是否为空队列,若是,队首队尾指针都指向新节点即可
} else {
q->rear->next=new_Node; //若否,则将新节点链接到q->rear,并更新队尾节点
q->rear=new_Node;
}
q->size++;
}
eletype QueuePop (Queue *q) {
if(q->front==NULL){
printf("Queue is empty!\n");
exit(1);
}
eletype result=q->front->data;
Node *temp=q->front;
q->front=q->front->next; //更新队首指针
free(temp); //定义一个*temp来接收q->front,并将其释放掉
q->size--;
return result;
}
eletype QueueTop (Queue *q) {
if(q->front==NULL){
printf("Queue is empty!\n");
exit(1);
}
return q->front->data;
}
int QueueGetsize (Queue *q) {
return q->size;
}
int main (){
Queue q;
QueueCreat (&q);
QueuePush (&q,10);
QueuePush (&q,20);
QueuePush (&q,30);
printf("出队元素为:%d\n",QueuePop (&q));
printf("队首元素为:%d\n",QueueTop (&q));
printf("队列的大小为:%d\n",QueueGetsize (&q));
}
总结
在完整源码调试的时候遇到了一个问题,其运行结果如下:
发现队首元素的输出有误!!!
后来发现问题出在释放空间的时候,
原错误代码:
eletype QueuePop (Queue *q) {
if(q->front==NULL){
printf("Queue is empty!\n");
exit(1);
}
eletype result=q->front->data;
Node *temp=q->front;
free(temp); //定义一个*temp来接收q->front,并将其释放掉
q->front=q->front->next; //更新队首指针
q->size--;
return result;
}
修改后的正确代码:
eletype QueuePop (Queue *q) {
if(q->front==NULL){
printf("Queue is empty!\n");
exit(1);
}
eletype result=q->front->data;
Node *temp=q->front;
q->front=q->front->next; //更新队首指针
free(temp); //定义一个*temp来接收q->front,并将其释放掉
q->size--;
return result;
}
很明显,将两句代码的执行顺序调换一下后(即前者是先释放空间后更新头指针。而后者是先更新头指针在释放空间),队首元素的输出就正确了。
这是什么原因呢?这个问题请帮忙大家想想看……
标签:Node,Queue,eletype,队首,C语言,链表,front,数据结构,rear From: https://blog.csdn.net/MaverickCoder/article/details/137190697