赞
踩
队列是一种常见的数据结构,它遵循先进先出(First-In-First-Out, FIFO)的原则,在队列的操作中入队从队列的尾部插入,出队的时候释放队列的头节点并且更新新的头节点。队列的存储方式主要有两种,分别是链式存储和顺序存储。每种存储方式都有其特点和适用场景。链式存储适合频繁进行插入和删除操作的队列,而顺序存储则适合频繁进行访问操作的队列。选择适当的存储方式要根据具体的应用需求和性能要求来决定。本篇主要介绍链式存储。
因为要用到链式存储的结构,因此需要定义结点结构体,以及队列的头尾指针。这里定义节点数据为int类型的data,结构体指针为next
- typedef struct Node{
- int data;
- struct Node* next;
- }Node; //结点结构体定义
-
- typedef struct{
- Node* front; //头指针
- Node* rear; //尾指针
- }Queue;
队列的初始化即分配一个节点内存,并且将头尾指针都指向这个空节点。
- //链队列初始化
- void Init_Queue(Queue* queue){
- //创建头节点
- queue->front = queue->rear = (Node*)malloc(sizeof(Node));
- if( !queue->front ){
- printf("内存分配失败\n");
- return;
- }
- }
入队列即在队尾插入一个新的节点,首先需要分配一块内存空间,将原来队尾指针指向新节点,并将新节点作为新的队尾。
- //入队列
- void Insert_Queue(Queue* queue,int value){
- Node* newCode;
- newCode = (Node*)malloc(sizeof(Node));
- if(newCode == NULL){
- printf("内存分配失败\n");
- return;
- }
- newCode->data = value;
- newCode->next = NULL;
- //判断是否是空队列
- if(queue->front == NULL){
- printf("该队列是空的\n");
- return;
- }
- //在尾部插入新节点
- queue->rear->next = newCode;
- //更新尾指针
- queue->rear = newCode;
- }
出队列的操作需要从队列的头进行,遵循先进先出的原理,因此需要将原来的头节点取出并释放,将下一个节点作为新的头节点。
- void Delete_Queue(Queue* queue){
- if(queue->front == NULL){
- printf("该队列是空的\n");
- return;
- }
- /*queue->front为头指针,指向的头节点*/
- Node* pout = queue->front;
- //更新头指针
- queue->front = queue->front->next;
- //若队列中仅剩一个结点时,删除了该节点后
- //队列就为空,此时应该从新初始化
- if(queue->front == NULL)
- queue->rear = NULL;
- //释放删除结点的内存
- free(pout);
- }
销毁一个队列就是在出队列的基础上进行一个循环,跳出循环的条件就是链队列的头指针为空,并且逐个节点进行释放,最后重置链队列的头尾节点。
- void Destroy_Queue(Queue* queue){
- Node* p = queue->front;
- while(p != NULL){
- Node* temp = p;
- p = p->next;
- free(temp);
- }
- printf("队列销毁成功!\n");
- //内存释放后指针重置,指向空
- queue->front = NULL;
- queue->rear = NULL;
- }
这里链队列的头指针指向了节点的头地址,因此要遍历打印队列需要从头指针的下一个节点开始。由于遍历链队列不需要对其进行修改,函数参数就不需要引用指针。
- void Print_Queue(Queue queue){
- if(queue.front == NULL){
- printf("该队列是空的\n");
- return;
- }
- Node* temp = queue.front->next;
- printf("该队列的内容为:\n");
- while(temp != NULL){
- printf("%d ",temp->data);
- temp = temp->next;
- }
- printf("\n");
- }
- int GetHead_Queue(Queue queue){
- if(queue.front == NULL){
- printf("该队列是空的\n");
- return -1;
- }
- return queue.front->next->data;
- }
主函数:
- void main(){
- //创建队列
- Queue queue;
- //队列初始化
- Init_Queue(&queue);
- //插入结点
- Insert_Queue(&queue,1);
- Insert_Queue(&queue,2);
- Insert_Queue(&queue,3);
- Print_Queue(queue);
- printf("该队列的头节点值为: %d \n",GetHead_Queue(queue));
-
- //删除结点
- Delete_Queue(&queue);
- Print_Queue(queue);
-
- //销毁队列
- Destroy_Queue(&queue);
- Print_Queue(queue);
- }
全部代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
-
- typedef struct Node{
- int data;
- struct Node* next;
- }Node; //结点结构体定义
-
- typedef struct{
- Node* front; //头指针
- Node* rear; //尾指针
- }Queue;
-
- //链队列初始化
- void Init_Queue(Queue* queue){
- //创建头节点
- queue->front = queue->rear = (Node*)malloc(sizeof(Node));
- if( !queue->front ){
- printf("内存分配失败\n");
- return;
- }
- }
-
- //入队列
- void Insert_Queue(Queue* queue,int value){
- Node* newCode;
- newCode = (Node*)malloc(sizeof(Node));
- if(newCode == NULL){
- printf("内存分配失败\n");
- return;
- }
- newCode->data = value;
- newCode->next = NULL;
- //判断是否是空队列
- if(queue->front == NULL){
- printf("该队列是空的\n");
- return;
- }
- //在尾部插入新节点
- queue->rear->next = newCode;
- //更新尾指针
- queue->rear = newCode;
- }
-
- void Delete_Queue(Queue* queue){
- if(queue->front == NULL){
- printf("该队列是空的\n");
- return;
- }
- /*queue->front为头指针,指向的头节点*/
- Node* pout = queue->front;
- //更新头指针
- queue->front = queue->front->next;
- //若队列中仅剩一个结点时,删除了该节点后
- //队列就为空,此时应该从新初始化
- if(queue->front == NULL)
- queue->rear = NULL;
- //释放删除结点的内存
- free(pout);
- }
-
- void Print_Queue(Queue queue){
- if(queue.front == NULL){
- printf("该队列是空的\n");
- return;
- }
- Node* temp = queue.front->next;
- printf("该队列的内容为:\n");
- while(temp != NULL){
- printf("%d ",temp->data);
- temp = temp->next;
- }
- printf("\n");
- }
-
- void Destroy_Queue(Queue* queue){
- Node* p = queue->front;
- while(p != NULL){
- Node* temp = p;
- p = p->next;
- free(temp);
- }
- printf("队列销毁成功!\n");
- //内存释放后指针重置,指向空
- queue->front = NULL;
- queue->rear = NULL;
- }
-
- int GetHead_Queue(Queue queue){
- if(queue.front == NULL){
- printf("该队列是空的\n");
- return -1;
- }
- return queue.front->next->data;
- }
-
- void main(){
- //创建队列
- Queue queue;
- //队列初始化
- Init_Queue(&queue);
- //插入结点
- Insert_Queue(&queue,1);
- Insert_Queue(&queue,2);
- Insert_Queue(&queue,3);
- Print_Queue(queue);
- printf("该队列的头节点值为: %d \n",GetHead_Queue(queue));
-
- //删除结点
- Delete_Queue(&queue);
- Print_Queue(queue);
-
- //销毁队列
- Destroy_Queue(&queue);
- Print_Queue(queue);
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。