write in front
个人主页:认真写博客的夏目浅石.
欢迎各位→点赞 + 收藏⭐️ + 留言
系列专栏:二、队列的结构
队列可以使用 数组 或 链表实现,但是二者之间有不同的地方,哪一个更加适合队列呢?
我想:使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数
组头上出数据,效率会比较低。三、队列的实现
3.1结构体的定义
typedef char QDatatype;typedef struct QueueNode{ struct QueueNode* next; QDatatype data;}QNode;
由于链表的尾插比较麻烦,而队列的入数据为尾插。所以定义队列的结构体时,可以定义两个指针
head
和tail
分别对应 队头 和 队尾 ,tail
的引入就是方便尾插再在给定一个size
实时记录队列的大小。typedef struct Queue{ QNode* head; QNode* tail; int size;}Queue;
3.2函数接口
void QueueInit(Queue* pq);//初始化void QueueDestroy(Queue* pq);//销毁void QueuePush(Queue* pq,QDatatype x);//入队列void QueuePop(Queue* pq);//出队列int QueueSize(Queue* pq);//计算队列大小bool QueueEmpty(Queue* pq);//判断队列是否为空QDatatype QueueFront(Queue* pq);//取对头元素QDatatype QueueBack(Queue* pq);//取队尾元素
3.3初始化
要领: 队列对头队尾相等都为NULL,且size=0;
void QueueInit(Queue* pq){ //暴力检查 assert(pq); pq->head=pq->tail=NULL; pq->size=0;}
3.4销毁
要领: 取
cur
不断遍历,然后free
节点,最后处理head
与tail
即可;void QueueDestroy(Queue* pq){ assert(pq); QNode* cur=pq->head; while(cur) { QNode* tmp=cur->next; free(cur); cur=tmp; } pq->head=pq->tail=NULL; pq->size=0;}
3.5入队列
要领: 尾节点(tail)进行插入;
void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}// 尾插if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++; }
3.6出队列
要领: 找到原本头节点的下一个节点 更换一下新的头节点就好了,注意free就行
void QueuePop(Queue* pq){ assert(pq); assert(pq->head!=NULL); QNode* tmp=pq->head->next; free(pq->head); pq->head=tmp; if(pq->head==NULL) { pq->tail=NULL; } pq->size--;}
3.7计算队列大小
要领: 返回size的大小即可;
int QueueSize(Queue* pq){ assert(pq); return pq->size;}
3.8判断队列是否为空
要领: 其实本质就是看size是否为0;
bool QueueEmpty(Queue* pq){ assert(pq); return pq->size==0;}
3.9取对头元素
要领: 队列非空,取 head 出数据
QDatatype QueueFront(Queue* pq){ assert(pq); assert(!QueueEmpty(pq)); return pq->head->data;}
3.10取队尾元素
要领: 队列非空,取 tail 处数据。
QDatatype QueueBack(Queue* pq){ assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data;}
四、队列的总代码
#include#include#include#includetypedef char QDatatype;typedef struct QueueNode{ struct QueueNode* next; QDatatype data;}QNode;typedef struct Queue{ QNode* head; QNode* tail; int size;}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDatatype x);void QueuePop(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);QDatatype QueueFront(Queue* pq);QDatatype QueueBack(Queue* pq);//--------------------------手动分割线---------------------------//初始化void QueueInit(Queue* pq){ //暴力检查 assert(pq); pq->head=pq->tail=NULL; pq->size=0;}//--------------------------手动分割线---------------------------//销毁void QueueDestroy(Queue* pq){ assert(pq); QNode* cur=pq->head; while(cur) { QNode* tmp=cur->next; free(cur); cur=tmp; } pq->head=pq->tail=NULL; pq->size=0;}//--------------------------手动分割线---------------------------void QueuePush(Queue* pq,QDatatype x){ assert(pq); QNode* newnode=(QNode*)malloc(sizeof(QNode)); if(newnode==NULL) { perror("malloc fail"); return; } newnode->data=x; newnode->next=NULL; if(pq->head==NULL) { assert(pq->tail==NULL); pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; } pq->size++;}//--------------------------手动分割线---------------------------void QueuePop(Queue* pq){ assert(pq); assert(pq->head!=NULL); QNode* tmp=pq->head->next; free(pq->head); pq->head=tmp; if(pq->head==NULL) { pq->tail=NULL; } pq->size--;}//--------------------------手动分割线---------------------------int QueueSize(Queue* pq){ assert(pq); return pq->size;}//--------------------------手动分割线---------------------------bool QueueEmpty(Queue* pq){ assert(pq); return pq->size==0;}//--------------------------手动分割线---------------------------QDatatype QueueFront(Queue* pq){ assert(pq); assert(!QueueEmpty(pq)); return pq->head->data;}//--------------------------手动分割线---------------------------QDatatype QueueBack(Queue* pq){ assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data;}
总结
今天学习了单链表的知识,初次写数据结构的知识,给我的感觉就是,学三遍不如手敲代码一遍来的实在,所以数据结构的学习我将
多画图,多敲代码来学习
,希望大家吸取经验和我一起学习数据结构,为后面打比赛刷题打下坚实基础。我是夏目浅石,希望和你一起学习进步,刷题无数!!!
希望各位大佬
能一键三连支持一下博主
,hhhh~我们下期见喽
如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn✨ 原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下
点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!
⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!