【数据结构】队列的简单理解和基本操作

AprilJ 发布于2021-09-02 15:40 / 1043人阅读

摘要：前言本章介绍的主要内容是数据结构中队列的概念，并通过代码实现链式结构的队列。

前言：本章介绍的主要内容是数据结构中队列的概念，并通过代码实现链式结构的队列。

文章目录

1.队列的基本概念

1.1 队列的定义

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性

1.2 队列的特点

队列是一种操作受限的线性表
队头(首)：允许删除的一端
队尾：允许插入的一端
空队列：没有元素的队列
删除操作叫做出队,插入操作叫做入队

2.队列的代码实现

程序名	功能
`Queue.h`	函数声明
`Queue.c`	功能函数的定义
`test.c`	测试

2.1 队列存储的说明

front指针:指向队头元素
rear指针:指向队尾元素的下一个位置
空队时：rear == front
队列初始化：rear = front = 0
入队：队未满时，先送值到队尾，再队尾指针加一
出队：队为空时，先取队头元素，再队头指针加一

2.2 队列的定义

这里选择实现链表链式结构的队列

链队本质上是一个同时带有队头指针、队尾指针的单链表
头指针指向队头结点
尾指针指向队尾结点
链式队列适合于数据元素变化较大的情形，不存在上溢
当使用多个队列时，最好使用链式队列，可以避免存储分配不合理下的溢出问题。

typedef int QDataType;typedef struct QueueNode  //定义队列结点{    QDataType data;    struct QueueNode* next;}QueueNode;typedef struct Queue   //定义队列{    QueueNode* head;  //队头    QueueNode* tail;  //队尾}Queue;

2.3 队列的初始化

直接初始化为NULL.

void QueueInit(Queue* pq){    assert(pq);    pq->head = pq->tail = NULL;}

2.4 队列的判空操作

只要头指针没有指向任何空间就说明队列为空

bool QueueEmpty(Queue* pq){    assert(pq);        return pq->head == NULL;}

2.5 队列的入队操作

因为咱们是链式结构，无需检查队列是否满了，直接开辟一个新空间存储数据，向新结点的数据域赋值，然后**tail->next指向新结点**。

void QueuePush(Queue* pq, QDataType elem){    assert(pq);    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));    if(newnode == NULL)    {        perror("空间申请:");        exit(-1);    }    newnode->data = elem;    newnode->next = NULL;        //检查队列是否为空    pq->head == NULL ? (pq->tail = newnode ):(pq->tail->next = newnode,pq->tail = pq->tail->next); }

2.6 队列的出队操作

1.先判断是否是空队,保存下一个结点

2.free释放头结点

3.指向所保存的下一个结点

（上述过程要小心出现队列内元素全部清完，pq->tail变成野指针的情况）

void QueuePop(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq));         QueueNode* next = NULL;        pq->head->next == NULL?    (free(pq->head),pq->head = pq->tail = NULL):    (next = pq->head->next, free(pq->head),pq->head = next);//避免野指针}

2.7 队列的获取队首元素操作

QDataType QueueFront(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq)); //不能为空        return pa->head->data;}

2.8 队列的获取队尾元素操作

QDataType QueueBack(Queue* pq){    assert(pq);    assert(!QueueEmpty(pq)); //不能为空        return pa->tail->data;}

2.9 队列的计算队列元素数量操作

直接遍历计数

int QueueSize(Queue* pq){    assert(pq);    int num = 0;    QueueNode* cur = pq->head;    while(cur)    {        num++;        cur = cur->next;    }    return num;}

2.10 队列的销毁操作

遍历free，最后记得置空

void QueueDestory(Queue* pq){	assert(pq);	QueueNode* cur = pq->head;	while (cur)	{		QueueNode* next = cur->next;		free(cur);		cur = next;	}	pq->head = pq->tail = NULL;}

3.源码链接

点击跳转源码仓库

数据结构的队列内容到此设计结束了，感谢您的阅读！！！如果内容对你有帮助的话，记得给我点个赞——做个手有余香的人。

服务器托管私有云云计算和大数据的理解 java 队列的操作简单理解超融合架构栈和队列的c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/118857.html

『并发包入坑指北』之阻塞队列

摘要：自己实现在自己实现之前先搞清楚阻塞队列的几个特点基本队列特性先进先出。消费队列空时会阻塞直到写入线程写入了队列数据后唤醒消费线程。最终的队列大小为，可见线程也是安全的。 showImg(https://segmentfault.com/img/remote/1460000018811340); 前言较长一段时间以来我都发现不少开发者对 jdk 中的 J.U.C（java.util.c...

nicercode 2019-08-19 11:36 评论0 收藏0
【Java实现】栈和队列就是这么简单

摘要：一前言上一篇已经讲过了链表实现单向链表了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦，如果有更好的理解的方式也希望能够在评论下留言，让大家学习学习二数据结构栈就是这么简单数据结构一、前言上一篇已经讲过了链表【Java实现单向链表】了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用：栈和队列如果写错的地方希望大家...

Ethan815 2019-08-16 11:09 评论0 收藏0
从浏览器多进程到JS单线程，JS运行机制最全面的一次梳理

摘要：如果看完本文后，还对进程线程傻傻分不清，不清楚浏览器多进程浏览器内核多线程单线程运行机制的区别。因此准备梳理这块知识点，结合已有的认知，基于网上的大量参考资料，从浏览器多进程到单线程，将引擎的运行机制系统的梳理一遍。前言见解有限，如有描述不当之处，请帮忙及时指出，如有错误，会及时修正。 ----------超长文+多图预警，需要花费不少时间。---------- 如果看完本文后，还...

wanghui 2019-08-22 13:56 评论0 收藏0
浏览器知识

摘要：浏览器的渲染进程是多线程的。异步请求线程在在连接后是通过浏览器新开一个线程请求将检测到状态变更时，如果设置有回调函数，异步线程就产生状态变更事件，将这个回调再放入事件队列中。 [TOC] 浏览器进程线程区分线程和进程 **- 什么是进程** 狭义定义：进程是正在运行的程序的实例（an instance of a computer program that is being exe...

Pluser 2019-08-23 15:37 评论0 收藏0
夯实基础-JavaScript异步编程

摘要：调用栈被清空，消息队列中并无任务，线程停止，事件循环结束。不确定的时间点请求返回，将设定好的回调函数放入消息队列。调用栈执行完毕执行消息队列任务。请求并发回调函数执行顺序无法确定。异步编程 JavaScript中异步编程问题可以说是基础中的重点，也是比较难理解的地方。首先要弄懂的是什么叫异步？我们的代码在执行的时候是从上到下按顺序执行，一段代码执行了之后才会执行下一段代码，这种方式...

shadowbook 2019-08-22 17:16 评论0 收藏0