服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言超详细讲解队列的实现及代码

C语言超详细讲解队列的实现及代码

2022-11-04 13:40三分苦 C/C++

队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。在队尾添加元素，在队头删除元素

前言

队列的概念

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

队列和前文所学的栈还是有一定区别的，队列明确指出先进先出。假如说一个队列的入队顺序为A B C D，那么出队顺序一定为A B C D，因为无论你是在A进去再出来，然后B进去再出来接着CD进去再出来或者类似的，都不会影响它最终的出队顺序A B C D。这点和栈还是有区别的，毕竟栈是后进先出。

队列的结构

C语言超详细讲解队列的实现及代码

队列的应用场景

队列：

  • 公平排队
  • 广度优先遍历 ……

栈：

  • 解决括号匹配
  • 逆波兰表达式求解
  • 递归改非递归 ……

队列的实现

  • 在实现之前，首先得考虑用哪种结构好，是用数组结构还是链式结构呢？上文的栈我们使用的是数组结构，难道队列也要用吗？
  • 其实不然。应该使用链式结构。前文栈删除数据不需要挪动数据，使用数组结构即可满足需求，而队列在删除数据时需要把后面的数据挪到前面，使用链式结构非常容易实现，只需改变节点指向即可，而数组结构想要实现挪动数据则非常麻烦。综上，使用链式结构是最优的。此外，单链表即可满足需求，不需要使用其余较为复杂的链式结构。

创建队列结构

思路：

这里要定义两个结构体，除了要定义1个链式结构来记录各个节点外，还要定义一个结构来记录队头和队尾。以此方便后续的队尾入数据，队头出数据。

Queue.h 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
 //创建队列节点
typedef struct QueueNode
{
    QDataType data; //存储数据
    struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
    QNode* head; //头指针
    QNode* tail; //尾指针
}Queue;

队列初始化  

思路：

队列可以为空，但是管理头指针和尾指针的结构体不能为空，所以一开始就要断言。其次，在插入数据前，队列肯定是空的，所以直接把头指针和尾指针置空即可。

Queue.h 文件：

?
1
2
//初始化队列
void QueueInit(Queue* pq);

Queue.c 文件：

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

队列销毁  

思路：

销毁队列就是把队列的每个数据都销毁掉，那么需要遍历链表进行挨个销毁free。首先定义一个cur指针为pq->head，用来保存第一个数据，遍历cur，如果不为空，就free。最后把tail和head置空即可。

Queue.h 文件：

?
1
2
//销毁队列
void QueueDestory(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
//销毁队列
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

入队列  

思路：

入队列其实很简单，只需要尾插即可，首先要新创建一个节点来保存新插入的数据。但是在尾插之前要考虑如果一开始队列没有数据，为空，那么只需要把head和tail节点指向新节点newnode节点即可。相反的，如果一开始就有数据，那么只需正常尾插把tail的next指向新节点newnode，再把newnode赋给tail即可。

C语言超详细讲解队列的实现及代码

Queue.h 文件：

?
1
2
//入队列
void QueuePush(Queue* pq, QDataType x);

 Queue.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//入队列
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    //创建一个新节点保存数据
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    //暴力检测newnode，因为malloc的都要检测
    assert(newnode);
    newnode->next = NULL;
    newnode->data = x;
    //如果一开始没有数据，为空的情况
    if (pq->tail == NULL)
    {
        assert(pq->head == NULL);
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

出队列  

思路：

特殊情况：

这里在删除数据时，首先要考虑特殊情况，当删到只剩一个数据时，再删一次，此时数据是没了，不过head为空了，而tail变成野指针了，为了避免此现象的产生，单独讨论并置空head和tail即可。

一般情况：

此时只需要定义一个next指针保存head的下一个节点，将head移动到next即可，并把旧的head置空。

C语言超详细讲解队列的实现及代码

 Queue.h 文件：

?
1
2
//出队列
void QueuePop(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//出队列
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head && pq->tail); //tail和head均不能为空
    //特殊：当删到head=tail的位置时
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    //一般情况
    else
    {
        //保存head的下一个节点
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

队列判空  

思路：

如果head为空或者tail为空都是判空的条件，直接返回即可。

Queue.h 文件：

?
1
2
//判空
bool QueueEmpty(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
//判空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

获取队列元素个数  

思路：

求元素个数其实不难，只需要定义一个cur指针为第一个数据pq->head，定义变量size来记录个数。依次遍历cur，不为空，size就++。这种遍历的思想不复杂，但时间复杂度达到O(N)，不是太好，想要O(1)的话可以直接在当初定义结构体时多定义一个size变量，专门用来记录有效元素个数，每次入队列size++，出队列size--。这样实现是比较好的，不过为了封装成一个独立模块，还是采用遍历的方式。如下：

Queue.h 文件：

?
1
2
//获取有效元素个数
size_t QueueSize(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

获取队列头部元素  

思路：

首先要断言头部不能为空，如果头部都为空了，那还怎么能获得头部元素，其次直接返回头部head的数据即可。

Queue.h 文件：

?
1
2
//获取队头元素
QDataType QueueFront(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
7
//获取队头元素
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head); //头部不能为空
    return pq->head->data;
}

获取队列尾部元素  

思路：

有了获取队头元素的经验，队尾就更简单了，把head换位tail即可，结构与上文一样。

Queue.h 文件：

?
1
2
//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件：

?
1
2
3
4
5
6
7
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail); //尾部不能为空
    return pq->tail->data;
}

总代码

Queue.h 文件

?
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
 //创建队列节点
typedef struct QueueNode
{
    QDataType data; //存储数据
    struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
    QNode* head; //头指针
    QNode* tail; //尾指针
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
 
//销毁队列
void QueueDestory(Queue* pq);
 
//入队列
void QueuePush(Queue* pq, QDataType x);
 
//出队列
void QueuePop(Queue* pq);
 
//判空
bool QueueEmpty(Queue* pq);
 
//获取有效元素个数
size_t QueueSize(Queue* pq);
 
//获取队头元素
QDataType QueueFront(Queue* pq);
 
//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件

?
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
 
//初始化队列
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}
 
//销毁队列
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}
 
//入队列
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    //创建一个新节点保存数据
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    //暴力检测newnode，因为malloc的都要检测
    assert(newnode);
    newnode->next = NULL;
    newnode->data = x;
    //如果一开始没有数据，为空的情况
    if (pq->tail == NULL)
    {
        assert(pq->head == NULL);
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}
 
//出队列
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head && pq->tail); //tail和head均不能为空
    //特殊：当删到head=tail的位置时
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    //一般情况
    else
    {
        //保存head的下一个节点
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}
 
//判空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}
 
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
 
//获取队头元素
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head); //头部不能为空
    return pq->head->data;
}
 
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail); //尾部不能为空
    return pq->tail->data;
}

Test.c 文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
    Queue q;
    QueueInit(&q);
    //插入数据
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    //打印
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    printf("\n");
}
int main()
{
    TestQueue();
    return 0;
}

到此这篇关于C语言超详细讲解队列的实现及代码的文章就介绍到这了,更多相关C语言 队列的实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/bit_zyx/article/details/123967787

  • C语言
  • 队列

    • 延伸 · 阅读

    精彩推荐
    • C/C++C++实现二维图形的傅里叶变换

      C++实现二维图形的傅里叶变换

      这篇文章主要介绍了C++实现二维图形的傅里叶变换的方法,是C++程序设计里一个重要的应用,需要的朋友可以参考下...

      C++教程网10342021-01-30
    • C/C++C/C++常用函数易错点分析

      C/C++常用函数易错点分析

      这篇文章主要介绍了C/C++常用函数易错点分析,包含了memset、sizeof、getchar三个常用函数的分析,需要的朋友可以参考下...

      C++教程网9062021-01-30
    • C/C++C++ STL中的容器适配器实现

      C++ STL中的容器适配器实现

      这篇文章主要介绍了C++ STL中的容器适配器实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随...

      一枚快乐的野指针12062021-11-02
    • C/C++C++调用Python基础功能实例详解

      C++调用Python基础功能实例详解

      c++调用Python首先安装Python，本文以win7为例，给大家详细介绍C++调用Python基础功能，需要的朋友参考下吧...

      yangzifb6312021-05-07
    • C/C++C++ 数据结构之kmp算法中的求Next()函数的算法

      C++ 数据结构之kmp算法中的求Next()函数的算法

      这篇文章主要介绍了C++ 数据结构之kmp算法中的求Next()函数的算法的相关资料,需要的朋友可以参考下...

      okbase7972021-05-19
    • C/C++C语言实现简易停车场管理系统

      C语言实现简易停车场管理系统

      这篇文章主要为大家详细介绍了C语言实现简易停车场管理系统，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      计算机小弟1110042022-10-20
    • C/C++C++友元(Friend)用法实例简介

      C++友元(Friend)用法实例简介

      这篇文章主要介绍了C++友元(Friend)用法,对于C++的学习来说有很好的参考价值,需要的朋友可以参考下...

      C++教程网8372021-01-29
    • C/C++分析C语言一个简单程序

      分析C语言一个简单程序

      本文主要介绍C语言简单的程序,这里给大家详细介绍C语言代码,对函数概念、头文件、自定义函数等基础信息的讲解,希望能帮助刚刚学习的同学...

      C语言中文网8602021-04-10
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 常量类型 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图