队列的概念及结构
队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 的原则。
- 入队列:进行插入操作的一端称为队尾。
- 出队列:进行删除操作的一端称为队头。
队列结构联想起来也非常简单,如其名,队列就相当于银行办理业务的柜台前一条长长的队伍,排在队伍前面的人(队头)可以先办理,而在队伍最后面的人(队尾)只能最后办理,如果继续有人来办理业务就只能排在队尾,这样的模式就是队列且遵循队头出队列,队尾入队列的原则。结构大致如下:
队列的实现
队列的实现同样有两种方式–数组队列,链式队列:
-
数组队列:
如果用数组实现队列:这样队头就只能指向下标为0
的位置,那么队尾就指向队列最后一个元素的后一个的下标,基于此结构,想要出队操作,时间复杂度就会升高为O(N)
且十分不方便。因为每当要将下标为0
的元素出队,后面的所有元素就要前移并改变队尾指向。大致如下:
还有一点就是,如果使用数组队列,在前期有大量数据入队列,动态开辟了很大的空间,到后期可能很多数据都出了队列但动态开辟的空间并不能释放,那就造成了严重的空间浪费。
-
链式队列:
如果使用双向链表: 这与栈为什么不用双向链表实现一个道理,虽然可以实现,且入队/出队的时间复杂度都为O(1)
但结构较为复杂,实现起来并不是很实用;
那么我们这时会选择结构更优得单链表,虽说单链表尾插得时间复杂度是O(N)
,但我们可以定义一个变量(QNode* ptail
)来记录单链表的尾节点,这样每次入队时便不用再遍历单链表找尾节点,时间复杂度也降为O(1)
。结构如下:
这样按需开辟空间,出队列就释放节点,进队列新建节点,也大大减少了空间的浪费。我们便可如下定义队列的每个节点:
typedef int QDataType;
//队列节点
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;//链接下一个节点的指针
}QNode;
因为我们要记录队列的头(QNode* phead
)和尾(QNode* ptail
)(下文称这两个指针为头指针和尾指针),且基本每个函数都要用到这两个变量,甚至一些函数还要修改这两个变量对应的值,那就不得不传二级指针了,这也就大大增加了代码的难度!为了解决这个问题,我们可以定义一个结构体,并将这两个变量放到结构体中,每次函数调用时,只需传这个结构体地址即可;
为了方便统计队列里面的节点数,我们通常还会定义一个整型变量size
,有元素出队列时size--
,入队列时size++
。
此结构体定义方式如下:
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
初始化
初始时队列中无节点,所以pq->size = 0
,头指针(pq->phead = NULL
)尾指针(pq->ptail = NULL
)都指向空。
//初始化
void QueueInit(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
)。
//入队列
void QueuePush(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--
)。
当队列只有一个节点时,删除后队尾和队头指针都应该指向空,但上述操作并不能达到此效果,所以要单独判断一下,将尾指针指向空。
//出队列
void QueuePop(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--;
}
其他一些队列函数
-
队列有效数据个数:
上面也讲过pq->size
记录的就是队列的有效数据个数
//数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
-
队列是否为空:
两种判断方法:1.当头指针指向NULL
,2.pq->size
的值为0
。
//队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
//return pq->size == 0;
}
-
返回队头数据:
首先要判断队列不为空,然后返回头指针指向的节点的val
即可。
//返回队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
-
返回队尾数据:
同上,首先要判断队列不为空,然后返回尾指针指向的节点的val
即可。
//返回队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->ptail->val;
}
-
释放队列空间:
遍历队列直到头指针指向空,每遍历一次释放一个节点,最后将头/尾指针指空,pq->size
置0
。
//释放
void QueueDetroy(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;
}
小结
- 队列是一种先进先出的结构,与栈相反;
- 队列是头部删除尾部插入,一般使用链表实现,且与栈结构一样不支持随机访问;
- 在实现队列时一般定义两个结构体,一个结构体用来记录每个节点中所需要的值,另一个用来记录队列的队头,队尾和节点数。第二个结构体的使用避免了二级指针,且在函数调用时一般传第二个结构体的地址。
队列相关题目
- 下面关于栈和队列的说法中错误的是( A B )
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”,栈是“先入后出”
这题主要考察对队列和栈的性质的区分,思路如下:
-
A错误:栈是尾部插入和删除,一般使用顺序表实现,队列是头部删除尾部插入,一般使用链表实现
-
B错误:栈是后进先出,尾部插入和删除;队列是先进先出,尾部插入头部删除
-
C正确:栈只能访问栈顶元素,不支持随机访问,队列也不支持
-
D正确:栈和队列的特性文章来源:https://www.toymoban.com/news/detail-753800.html
关于队列还有一个知识点就是循环队列,因其结构复杂就单独拿出来讲。文章来源地址https://www.toymoban.com/news/detail-753800.html
到了这里,关于【数据结构和算法】--队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!