自己做网站 什么软件,微信公众平台视频网站开发,软件开发需要的软件,百度站长 添加网站目录
队列的基本概念
队列的实现
头文件queue.h
实现函数接口
1.初始化和销毁
2.出队列和入队列
3.获取队头元素和队尾元素
4.队列长度判空
后记 前言 欢迎大家来到小鸥的博客~ 个人主页#xff1a;海盗猫鸥 本篇专题#xff1a;数据结构 多谢大家的支持啦#xff…目录
队列的基本概念
队列的实现
头文件queue.h
实现函数接口
1.初始化和销毁
2.出队列和入队列
3.获取队头元素和队尾元素
4.队列长度判空
后记 前言 欢迎大家来到小鸥的博客~ 个人主页海盗猫鸥 本篇专题数据结构 多谢大家的支持啦 上一篇关于数据结构的博客中我们讲解了栈本篇我们就来讲讲队列吧
队列的基本概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
如果使用数组每次出队列之后都需要移动数据消耗较大。
所以本篇使用单链表实现队列因为头删和尾插刚好可以满足队列的需要单链表消耗最大的就是尾删后遍历查找新尾节点但队列不需要尾删所以不存在这个问题。
队列的入队列顺序和出队列顺序一定是相同的。
队列的实现
队列的C语言实现我们要实现的函数和实现栈是差不多的 只是其存放数据的数据结构变为了一个链表
头文件queue.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int QueueDataType;typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化和销毁
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入队列和出队列
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);//队头元素和队尾元素
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);//队列长度函数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
这里我们除了定义了链表节点的结构体QueueNode之外我们还额外创建了一个Queue的结构体这个结构体是用来存放队列的一些信息的phead指向队头ptail则指向队尾这样进行入栈和出栈的操作时就可以直接通过这俩个指针直接对链表进行头删和尾插操作从而实现出队列和入队列操作size则表示队列的数据个数。
实现函数接口
1.初始化和销毁
因为我们是通过Queue结构体来操作队列的所以不论初始化还是后面的函数都需要的是Queue*类型的指针
//初始化和销毁
void QueueInit(Queue* pq)
{assert(pq);pq-size 0;pq-phead pq-ptail NULL;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
由于是本质是一个链表结构所以在释放空间时需要遍历链表进行释放。
2.出队列和入队列
队列入数据只能从队尾插入出数据只能从队头出。
//入队列(尾插)
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);//动态申请空间创建空间QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail!);return;}newnode-data x;newnode-next NULL;//没有节点时if (pq-ptail NULL){pq-phead pq-ptail newnode;}else//存在节点{pq-ptail-next newnode;pq-ptail newnode;}//队列长度pq-size;
}
//出队列(头删)
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead ! NULL);//只有一个节点if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else//多个节点{QNode* newhead pq-phead-next;free(pq-phead);pq-phead newhead;}pq-size--;
}
入队列和出队列就是运用的链表的尾插和头删的逻辑。
3.获取队头元素和队尾元素
//队头元素和队尾元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead ! NULL);return pq-phead-data;
}
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail ! NULL);return pq-ptail-data;
}
由于我们的Queue结构体中就存储了队头和队尾的地址所以这两个函数就可以直接返回对应的数据。
4.队列长度判空
//队列长度函数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return !(pq-size);
}
Queue结构体中的size就是在这里起作用的如果没有size这个成员就需要遍历链表来实现。
后记
本篇队列的介绍和C语言实现就结束啦
下篇我们将讲解几道栈和队列的相关OJ题大家不见不散哦
那么我们下次见~
