首页 > 其他分享 >队列-数据结构

队列-数据结构

时间:2024-09-06 18:54:45浏览次数:14  
标签:Queue NULL qnode 队列 queue 数据结构 data

一、队列 FIFO

特点:先进先出,后进后出

允许从一段插入数据,另一端删除数据的线性存储结构

队尾:插入数据 入队

队头:删除数据 出队

管道实质上也是一个队列。

用途:缓存数据(主要是避免两者速度不匹配的,数据存取速度不匹配。)

二、队列类型
2.1、顺序队列

顺序队列---------》假溢出-----------------》循环队列(如果用顺序队列里面,我们主要用的就是循环队列)

队列中的假溢出是指当队列的存储空间实际上还有空闲位置时,由于队列的访问限制导致无法插入新的元素,从而表现出“溢出”的假象。在循环队列中,这种情况尤为常见。

循环队列是一种使用数组存储数据元素的线性数据结构,它利用数组的环状特性来处理队列的入队和出队操作。在循环队列中,通常有两个指针front和rear分别指向队列的第一个元素和最后一个元素的下一个位置。队列的空和满的条件是相同的,都是(rear + 1) % queueSize == front,其中queueSize是队列的容量。因此,当队列满时,即使数组中有空间,也会因为队列的规则认为它已经满了,无法再添加新元素,这时如果尝试入队,就会产生假溢出。

解决假溢出的方法

为了避免假溢出,可以在定义循环队列的时候预留一个位置,通常在初始化队列时,将front和rear都设置为0,但在判断队列满的条件中加入一个额外的判断条件,比如rear == front时队列为空,而(rear + 1) % queueSize == front时队列为满。

2.2、链式队列

1、创造队列

Queue_t *create_queue()
{
    Queue_t *queue = malloc(sizeof(Queue_t));
    if(queue == NULL)
    {
        return NULL;
    }
    queue->pfront = NULL;
    queue->prear = NULL;
    queue->clen =0;
    pthread_mutex_init(&(queue->mutex),NULL);
    return queue;
}

2、入队

int push_queue(Queue_t *queue,QDataType data)
{
    QNode_t *qnode = malloc(sizeof(QNode_t));
    if(qnode == NULL)
    {
        perror("malloc fail");
        return -1;
    }
    qnode->data = data;
    qnode->pnext = NULL;
    if(is_empty_queue(queue))
    {
        queue->prear = qnode;
        queue->pfront = qnode;
    }
    queue->prear->pnext = qnode;
    queue->prear = qnode;
    queue->clen++;
    return 0;
}

3、出队

int pop_queue(Queue_t *queue,QDataType *data)
{
    if(is_empty_queue(queue))
    {
        return 0;
    }
    QNode_t *qnode = queue->pfront;
    queue->pfront = qnode->pnext;
    if(data != NULL)
    {
        *data = qnode->data;
    }
    free(qnode);
    if(NULL == queue->pfront)
    {
        queue->prear = NULL;
    }
    queue->clen--;
    return 0;
}

4、得到队头元素

int get_queue_front(Queue_t *queue,QDataType *data)
{
    QNode_t *q = queue->pfront;
    *data = q->data;
    return 0;
}

5、清空队列

void clear_queue(Queue_t *queue)
{
    while(!is_empty_queue(queue))
    {
        pop_queue(queue,NULL);
        /*
        QNode_t *qnode = queue->pfront;
        queue->pfront = qnode->pnext;
        free(qnode);
        queue->clen--;*/
    }
}

6、销毁队列

    void destory_queue(Queue_t *queue)
{
    clear_queue(queue);
    free(queue);
}

标签:Queue,NULL,qnode,队列,queue,数据结构,data
From: https://blog.csdn.net/weixin_63722559/article/details/141963676

相关文章

  • 数据结构-绪论
    1.可以用抽象数据类型定义有一个完整的数据类型。抽象数据类型包括数据对象,数据关系,抽象运算。数据结构:逻辑结构+数据运算。2.有序表属于逻辑结构。有序表是一种逻辑结构,它只描述了数据元素之间的逻辑关系,而与实际的物理存储方式无关。这种逻辑上的有序性意味着表中的元素......
  • 数据结构练习题(java版)考前必备!
    今天我们刷一些栈队列的题目,大家还是先看题,后看题解。1.155.最小栈-力扣(LeetCode)思路:创建两个栈,一个栈所有元素都算,另一个栈只放小的元素,第二个栈中如果要放的元素比栈顶的元素小就放,这样我们直接pop第二个栈就能得到最小栈classMinStack{publicStack<Integer>......
  • 记录 ThreadPoolExecutor任务队列放入任务的方式
    众所周知,ThreadPoolExecutor内部任务队列属性类型定义为:privatefinalBlockingQueueworkQueue;而其有三种提交任务方式:add、put和offer,好奇其内部用的哪个,又不想查资料,故而跳到源码内部一看。结果如下:三种提交任务方式:put(Eelement):将指定元素插入队列,如果队列已满,则阻塞......
  • Java数据结构---Queue
    队列Queue队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。入队列(Enqueue):进行插入操作的一端称为队尾出队列(Dequeue):进行删除操作的一端称为队头队列具有先进先出的特性大家可以简单理解为日常生活中“排队”这一现象。队列的模拟实现简单想一想,因为Lin......
  • 数据结构-栈、队列-相关练习
    数据结构-栈、队列-相关练习1.用队列实现栈2.用栈实现队列3.设计循环队列1.用队列实现栈用队列实现栈题目概述:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop和empty)。这里只讲大致思路,如下图:互相倒就行了,下面讲个具体......
  • 软设每日打卡——霍夫曼编码将频繁出现的字符釆用短编码,出现频率较低的字符采用长编码
    【题目】霍夫曼编码将频繁出现的字符釆用短编码,出现频率较低的字符采用长编码。具体        的操作过程为:i)以每个字符的出现频率作为关键字构建最小优先级队列;ii)取出关键        字最小的两个结点生成子树,根节点的关键字为孩子节点关键字之和,并将根节点......
  • 代码随想录算法训练营第十天| 232.用栈实现队列 、 225. 用队列实现栈 、20. 有效的括
    学习文章链接:代码随想录文章目录一、232.用栈实现队列二、225.用队列实现栈三、20.有效的括号四、1047.删除字符串中的所有相邻重复项一、232.用栈实现队列题目链接:232.用栈实现队列栈的操作:stack<int>s;s.empty();//如果栈为空则返回true,......
  • PART1-Oracle关系数据结构-数据完整性
    5.数据完整性5.1.数据完整性简介5.1.1.保证数据完整性的技术5.1.2.完整性约束的优势5.2.完整性约束的类型5.2.1.非空完整性约束5.2.2.唯一性约束5.2.3.主键约束5.2.4.外键约束5.2.5.检查约束5.3.完整性约束状态5.3.1.对已修改和现有数据的检查5.3.2.可延......
  • 一文看懂数据结构7种查询算法
    常见的七种查找算法:​数据结构是数据存储的方式,算法是数据计算的方式。所以在开发中,算法和数据结构息息相关。今天的讲义中会涉及部分数据结构的专业名词,如果各位铁粉有疑惑,可以先看一下哥们后面录制的数据结构,再回头看算法。1.基本查找​也叫做顺序查找​说明:顺序......
  • freeRTOS面试题目 面经 单片机面经汇总MCU RTOS常见面试经验汇总 freeRTOS消息队列 信
    常见rtos部分Linux题目汇总FreeRtos面经30题前后台程序与实时操作系统的区别是什么?实时系统的基本特性有哪些?什么是不可剥夺型内核?它的特点是什么?可剥夺型内核的定义及适用场景是什么?什么是可重入型函数?它有什么特点?使用可剥夺型内核时,为什么不应直接使用不可重入型函数......