文章目录
- 前言
- 一、什么是队列?
- 二、队列接口的实现
- 1.队列结构的定义
- 2.接口实现
- 总结
前言
队列是一种特殊的线性表。
特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。
进行插入操作的端称为队尾,进行删除操作的端称为队头。
队列中没有元素时,称为空队列。
队列的数据元素又称为队列元素。
在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。
因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表
一、什么是队列?
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。
队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
二、队列接口的实现
1.队列结构的定义
//队列--先进先出--用链表实现
typedef int QDataType;//队列的单节点定义
typedef struct QNode
{QDataType val;struct QNode* next;
}QNode;//队列整体定义,有头,尾,以及元素个数
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
原因:队列使用链表实现,使其每个节点的定义为链表节点形式,而因为队列是一个线性结构,需要有头尾节点进行访问,而且还需要返回其元素个数,便于某些特定场合下的访问,需要将其封装到结构体中,便于访问,因而定义两个结构体形式。
2.接口实现
1. 初始化
//初始化
void QInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
为什么加断言?
可以明确的知道,pq指针不为空,则需要进行断言,避免他人传错参数。
2. 销毁
//销毁
void QDestroy(Queue* pq)
{//空队列没必要销毁assert(pq);assert(pq->head != NULL);//依次进行释放QNode* cur = pq->head;while (cur){QNode* after = cur->next;free(cur);cur = after;}pq->head = pq->tail = NULL;pq->size = 0;
}
因为是从堆上动态开辟出来的节点,需要依次释放,避免一次性释放,无法找到剩下的节点,导致出现内存泄漏。
3. 插入(入队)
//插入--入队列
void QPush(Queue* pq, QDataType x)
{assert(pq);//开辟一个新的节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;//链接--尾插if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
入队过程:1.进行新节点的开辟,需要对malloc的结果进行检查,有备无患
2.有了新节点,需要进行链接过程,链接过程中,需要进行对于队列头尾指针的检查,避免出现非法访问的情况,因为在初始化过程,对于head和tail是赋为空指针的
3.检查完是否为空指针后,即开始链接,也就是进行普通的尾插过程。
4. 删除(出队列)
//删除--出队列
void QPop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//因为队列的性质,先进先出,则其删除是头删QNode* after = pq->head->next;free(pq->head);pq->head = after;pq->size--;
}
出队列过程:普通的头删即可,但是,需要注意的是空队列无需删除,需要对head进行判断,否则会出现非法访问情况
5. 获取元素个数
//返回队列元素个数
int QSize(Queue* pq)
{assert(pq);return pq->size;
}
很普通的操作,但是在某些特定的环境下,可以发挥出神奇的效果,可以使得获取元素效率很快
6. 获取队头和队尾元素及判空
//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//取队头元素
QDataType QFront(Queue* pq)
{assert(pq);//空队列不用取元素assert(!QEmpty(pq));return pq->head->val;}//取队尾元素
QDataType QRear(Queue* pq)
{assert(pq);//空队列不用取元素assert(!QEmpty(pq));return pq->tail->val;
}
判空和获取队头队尾元素配合使用,因为空的队列无法获取元素
总结
队列,数据结构中的特殊结构,具有先进先出的特性,使得在某些场合会被频繁利用,所以对于身为学习者的我们,需要掌握其实现逻辑和实现方法。