【数据结构】带你深入栈和队列，轻松实现各种接口功能

君兮_的个人主页

勤时当勉励 岁月不待人

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，我们继续来学习初阶数据结构的内容，今天我们要讲的是栈与队列内容中队列部分的内容
好了，废话不多说，开始今天的学习吧！—

二.队列

1.队列的概念及结构

• 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
• 入队列：进行插入操作的一端称为队尾
  出队列：进行删除操作的一端称为队头
  

2.队列的实现

• 队列也可以使用数组和链表的结构实现，实际上使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
• 因此在下面的讲解中，我们通过链表来实现

队列的基本结构

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
1
2
3
4
5
6
7
8
9
10
11
12
13

• 在队列的实现中与之前最大的不同是我们使用了两个结构体，其中第一个保存链表的存储的元素以及地址，而第二个保存的则是队列的头和尾的指针，这样有什么意义呢？
• 在队列中，我们常常需要获取队列保存元素的多少，同时我们又需要实现队列的先进先出，也就是尾插进，头插出，这样如果我们没有一个能够指向尾部的指针，每次都需要通过遍历一下我们这个链表队列来找尾，这无疑不利于程序运行，因此我们定义第二个结构体来找尾。

队列的初始化 QueueInit

//初始化队列
void QueueInit(Que* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
1
2
3
4
5
6
7

• 初始化非常简单啊，无法是指针置空，让队列元素size置0就行，不多解释啦

往队列中插入元素 QueuePush

//把结点插入队列中(尾插)
void QueuePush(Que* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));//malloc申请空间
    if (newnode == NULL)//判断申请是否成功
    {
        perror("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;//插入元素
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;//如果此时队列中没有元素就把头和尾都指向开辟出来的空间
    }
    else
    {
    	//尾插
        pq->tail->next = newnode;
        pq->tail = newnode;
        
    }
    pq->size++;//插入元素成功，有效元素个数加1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 上面这个图很形象的画出了入队和出队的情况，就不像之前详细的每一过程都用逻辑图带大家逐一分析了，大家结合这张图以及代码中的注释我相信非常好理解这个部分。

删除队列中的元素 QueuePop

// 删除队列中某个结点
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--;//队列中有效元素减1

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

判断队列是否为空 QueueEmpty

//判断队列是否为空
bool QueueEmpty(Que* pq)
{
    assert(pq);
    return pq->tail == NULL;
}
1
2
3
4
5
6

• 这里利用返回bool的函数来判断我们的尾是否为0，为0说明此时的队列中没有元素，队列为空返回true，如果尾指针不为0说明队列不为空就返回false

获取队列中的队头元素 QueueFront

//获取队列的队头元素
QDataType QueueFront(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    QNode* cur = pq->head;
    return cur->data;
}

1
2
3
4
5
6
7
8
9

• 队头元素就是头指针指向的结点，返回头指针存储的元素即可

获取队尾的元素 QueueBack

//获取队列的队尾元素
QDataType QueueBack(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
1
2
3
4
5
6
7

• 这里就体现了我们使用两个结构体的优势，我们通过尾指针就可以直接指向队尾，返回队尾的元素即可

队列的销毁 QueueDestroy

//队列的销毁
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;//有效元素置0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 我们通过遍历队列链表中每一个结点来销毁我们的队列，当head为空时，说明我们链表中的结点已经全部被销毁，队列的销毁完成

计算队列元素的数量

//计算队列的元素的数量
int QueueSize(Que* pq)
{
    return pq->size;
}
1
2
3
4
5

• 我们每次进行入队或者出队时，都会让有效元素size+1或者-1，因此此时需要获取队列元素的数量时，返回size即可。

总结

• 今天的内容到这里就结束了，栈与队列的最大区别在于栈是后进先出，而队列是先进先出，两者在实现中实际都并没有那么难，如果你想学好这部分内容的话，不妨自己照着上面的内容试试吧！
• 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！

新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！

**（可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧）**