数据结构队列
目录
数据结构（队列）
数据结构（队列）
什么是队列？
- 队列和栈类似，也是一类特殊的线性表。特殊之处也是在于操作上。
- 队列：只允许在一端进行插入数据操作（入队），在另一端进行删除数据操作（出队）的特殊的线性表。
- 具有先进先出，后进后出的特点。
- 进行插入操作（入队）的一端称为队尾。进行删除操作（出队）的一端称为队头。
队列的意义（作用）
队列的实现
- 和栈类似，也有两种实现方式。一种是数组，也就是顺序表，一种是链表。
- 两种方式都是可以的，不过相比之下，链表更优一些。
- 因为队列是在队头出数据，也就是头部删除数据，那么顺序表要删除头部数据需要一个个的移动数据进行覆盖。所以我们优先选择链表实现。
链表类型的选择
实现代码
- 头文件.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType date; }QNode; typedef struct Queue { QNode * head; QNode * tail; int size; }Que; //队列初始化 void QueueInit(Que* pq); //队列销毁 void QueueDestroy(Que* pq); //入队（尾部插入数据） void QueuePush(Que* pq,QDateType x); //出队（头部删除数据） void QueuePop(Que* pq); //获得队头节点的值 QDateType QueueFront(Que* pq); //获得队尾节点的值 QDateType QueueBack(Que* pq); //判断队列是否为空 bool QueueEmpty(Que* pq); //获得队列的长度（有效元素个数） int QueueSize(Que* pq);
- 函数实现文件.c
#include "Queue.h" //队列初始化 void QueueInit(Que* pq) { assert(pq); pq->head=pq->tail=NULL; pq->size=0; } //队列销毁 void QueueDestroy(Que* pq) { assert(pq); QNode* cur=pq->head; while(cur) { QNode *next=cur->next; free(cur); cur=next; } pq->head=pq->tail=NULL; pq->size=0; } //入队（尾部插入数据） void QueuePush(Que* pq,QDateType x) { assert(pq); QNode *newnode=(QNode*) malloc(sizeof (QNode)); if(newnode==NULL) { perror("malloc failed"); exit(-1); } newnode->next=NULL; newnode->date=x; if(pq->tail==NULL) { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; } pq->size++; } //出队（头部删除数据） void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if(pq->head->next==NULL) { free(pq->head); pq->head=pq->tail=NULL; } else { QNode *next=pq->head->next; free(pq->head); pq->head=next; } pq->size--; } //获得队头节点的值 QDateType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->date; } //获得队尾节点的值 QDateType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->date; } //判断队列是否为空 bool QueueEmpty(Que* pq) { assert(pq); return pq->head==NULL; } //获得队列的长度（有效元素个数） int QueueSize(Que* pq) { assert(pq); return pq->size; }
函数解析
- 队列结构
typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType date; }QNode; typedef struct Queue { QNode * head; QNode * tail; int size; }Que;
- 队列初始化
//队列初始化 void QueueInit(Que* pq) { assert(pq); pq->head=pq->tail=NULL; pq->size=0; }
- 队列销毁
//队列销毁 void QueueDestroy(Que* pq) { assert(pq); QNode* cur=pq->head; while(cur) { QNode *next=cur->next; free(cur); cur=next; } pq->head=pq->tail=NULL; pq->size=0; }
- 入队（尾部插入数据）
//入队（尾部插入数据） void QueuePush(Que* pq,QDateType x) { assert(pq); QNode *newnode=(QNode*) malloc(sizeof (QNode)); if(newnode==NULL) { perror("malloc failed"); exit(-1); } newnode->next=NULL; newnode->date=x; if(pq->tail==NULL) { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; } pq->size++; }
- 出队（头部删除数据）
//出队（头部删除数据） void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if(pq->head->next==NULL) { free(pq->head); pq->head=pq->tail=NULL; } else { QNode *next=pq->head->next; free(pq->head); pq->head=next; } pq->size--; }
- 获得队头节点的值
//获得队头节点的值 QDateType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->date; }
- 这个不多说。
- 获得队尾节点的值
//获得队尾节点的值 QDateType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->date; }
- 不多说了。
- 判断队列是否为空
//判断队列是否为空 bool QueueEmpty(Que* pq) { assert(pq); return pq->head==NULL; }
- 连头都没有，那是不是空的？或者pq->tail==NULL。也可以判空。
- 获得队列的长度（有效元素的个数）
//获得队列的长度（有效元素个数） int QueueSize(Que* pq) { assert(pq); return pq->size; }
- 不多说，每次插入删除数据，都会带上它变化的。它就是用来记录元素个数的。
- 那么队列的基本知识就基本完成了。