队列的基本操作

2024-07-10 17:31| 来源: 网络整理| 查看: 265

什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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; }

【本文地址】

队列的基本操作

队列的基本操作

今日新闻

推荐新闻