【数据结构和算法】--队列

目录

队列的概念及结构

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的原则。

• 入队列：进行插入操作的一端称为队尾。
• 出队列：进行删除操作的一端称为队头。

队列结构联想起来也非常简单，如其名，队列就相当于银行办理业务的柜台前一条长长的队伍，排在队伍前面的人（队头）可以先办理，而在队伍最后面的人（队尾）只能最后办理，如果继续有人来办理业务就只能排在队尾，这样的模式就是队列且遵循队头出队列，队尾入队列的原则。结构大致如下：

队列的实现

队列的实现同样有两种方式–数组队列，链式队列：

1. 数组队列：如果用数组实现队列：这样队头就只能指向下标为0的位置，那么队尾就指向队列最后一个元素的后一个的下标，基于此结构，想要出队操作，时间复杂度就会升高为O(N)且十分不方便。因为每当要将下标为0的元素出队，后面的所有元素就要前移并改变队尾指向。大致如下：

还有一点就是，如果使用数组队列，在前期有大量数据入队列，动态开辟了很大的空间，到后期可能很多数据都出了队列但动态开辟的空间并不能释放，那就造成了严重的空间浪费。

1. 链式队列：如果使用双向链表： 这与栈为什么不用双向链表实现一个道理，虽然可以实现，且入队/出队的时间复杂度都为O(1)但结构较为复杂，实现起来并不是很实用； 那么我们这时会选择结构更优得单链表，虽说单链表尾插得时间复杂度是O(N)，但我们可以定义一个变量（QNode* ptail）来记录单链表的尾节点，这样每次入队时便不用再遍历单链表找尾节点，时间复杂度也降为O(1)。结构如下：

这样按需开辟空间，出队列就释放节点，进队列新建节点，也大大减少了空间的浪费。我们便可如下定义队列的每个节点：

typedefint QDataType;//队列节点typedefstructQueueNode{
    QDataType val;structQueueNode* next;//链接下一个节点的指针}QNode;

因为我们要记录队列的头（

QNode* phead

）和尾（

QNode* ptail

）（下文称这两个指针为头指针和尾指针），且基本每个函数都要用到这两个变量，甚至一些函数还要修改这两个变量对应的值，那就不得不传二级指针了，这也就大大增加了代码的难度！为了解决这个问题，我们可以定义一个结构体，并将这两个变量放到结构体中，每次函数调用时，只需传这个结构体地址即可；
为了方便统计队列里面的节点数，我们通常还会**定义一个整型变量

size

**，有元素出队列时

size--

，入队列时

size++

。
此结构体定义方式如下：

typedefstructQueue{
    QNode* phead;
    QNode* ptail;int size;}Queue;

初始化

初始时队列中无节点，所以

pq->size = 0

，头指针（

pq->phead = NULL

）尾指针（

pq->ptail = NULL

）都指向空。

//初始化voidQueueInit(Queue* pq){assert(pq);
    pq->size =0;
    pq->phead = pq->ptail =NULL;}

入队

入队操作首先要新建一个节点（类型为

QNode

），然后通过尾指针指向的节点链接此节点（

pq->ptail->next = newnode

），并更新尾指针的指向（

pq->ptail = newnode

），将记录节点数的值加1（

pq->size++

）。
在链接时还要考虑到队列为空的情况，此情况下直接将头/尾指针指向新建的节点（

pq->ptail = pq->phead = newnode

）。

//入队列voidQueuePush(Queue* pq, QDataType x){assert(pq);//新建节点
    QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("QueuePush()::malloc");return;}//新建的节点初始化
    newnode->next =NULL;
    newnode->val = x;//判断，链接if(pq->ptail ==NULL){//1.原队列无节点
        pq->ptail = pq->phead = newnode;}else{//2.原队列已有节点
        pq->ptail->next = newnode;
        pq->ptail = newnode;}
    pq->size++;}

出队

出队列操作首先要确保队列有节点才能出队，那么断言一下就可（

assert(pq->phead);

）。需要注意的是出队是头删，可以先定义变量记录头节点（

QNode* del = pq->phead;

），然后再将头指针指向下一个节点（

phead = phead->next;

），最后将原头节点释放（

free(del);

），并将记录节点数的值减1（

pq->size--

）。
当队列只有一个节点时，删除后队尾和队头指针都应该指向空，但上述操作并不能达到此效果，所以要单独判断一下，将尾指针指向空。

//出队列voidQueuePop(Queue* pq){assert(pq);//队列不为空assert(pq->phead);
    QNode* del = pq->phead;//记录头节点
    pq->phead = pq->phead->next;//头指针重定向free(del);//释放原头节点
    del =NULL;//队列是否被删空判断if(pq->phead ==NULL)
        pq->ptail =NULL;
    pq->size--;}

其他一些队列函数

1. 队列有效数据个数： 上面也讲过pq->size记录的就是队列的有效数据个数

//数据个数intQueueSize(Queue* pq){assert(pq);return pq->size;}

1. 队列是否为空：****两种判断方法：1.当头指针指向NULL，2.pq->size的值为0。

//队列是否为空
bool QueueEmpty(Queue* pq){assert(pq);return pq->phead ==NULL;//return pq->size == 0;}

1. 返回队头数据： 首先要判断队列不为空，然后返回头指针指向的节点的val即可。

//返回队头数据
QDataType QueueFront(Queue* pq){assert(pq);assert(pq->phead);return pq->phead->val;}

1. 返回队尾数据： 同上，首先要判断队列不为空，然后返回尾指针指向的节点的val即可。

//返回队尾数据
QDataType QueueBack(Queue* pq){assert(pq);assert(pq->phead);return pq->ptail->val;}

1. 释放队列空间： 遍历队列直到头指针指向空，每遍历一次释放一个节点，最后将头/尾指针指空，pq->size置0。

//释放voidQueueDetroy(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;}

小结

• 队列是一种先进先出的结构，与栈相反；
• 队列是头部删除尾部插入，一般使用链表实现，且与栈结构一样不支持随机访问；
• 在实现队列时一般定义两个结构体，一个结构体用来记录每个节点中所需要的值，另一个用来记录队列的队头，队尾和节点数。第二个结构体的使用避免了二级指针，且在函数调用时一般传第二个结构体的地址。

队列相关题目

1. 下面关于栈和队列的说法中错误的是（ A B ） A.队列和栈通常都使用链表实现 B.队列和栈都只能从两端插入、删除数据 C.队列和栈都不支持随机访问和随机插入 D.队列是“先入先出”，栈是“先入后出”

这题主要考察对队列和栈的性质的区分，思路如下：

• A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现
• B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除
• C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持
• D正确：栈和队列的特性

关于队列还有一个知识点就是循环队列，因其结构复杂就单独拿出来讲。