• 【数据结构】队列的使用方法


    队列(Queue)是另一种基本的线性数据结构,它允许在一端进行插入操作,而在另一端进行删除操作。队列的特点是先进先出(First In First Out, FIFO),即最先进入队列的元素最先被取出。

    队列可以用数组来实现,也可以用链表来实现。用数组实现的队列称为顺序队列,用链表实现的队列称为链式队列。

    顺序队列的特点是:

    • 存储空间连续。
    • 提前分配固定大小的存储空间,可能会造成空间浪费,或者空间不足时需要动态扩容。
    • 访问速度快,因为支持随机访问。

    链式队列的特点是:

    • 存储空间不连续。
    • 动态分配空间,不会造成空间浪费,也不会出现空间不足的问题。
    • 访问速度相对较慢,因为不支持随机访问。

    队列的应用非常广泛,包括:

    • 任务调度:在多任务操作系统中,队列用于管理等待执行的线程或进程。
    • 缓冲处理:在网络通信中,队列用于临时存储数据包,以平滑网络拥塞。
    • 异步数据传输:在消息队列中,生产者将消息放入队列,消费者从队列中取出消息,实现异步处理。
    • 事件管理:在图形用户界面中,队列用于管理用户操作产生的事件。

    队列是一种简单但重要的数据结构,它在管理需要按照特定顺序处理的元素集合时非常有用。

    以下我讲以下顺序队列的基本使用方法。 

    1.循环队列结构体定义

    #define N 10
    typedef struct
    {
            int data [ N ];
            int front ; // 队头,删除出队时用 front 当下标
            int rear ; // 队尾,插入入队时用 rear 当下标
    } queue_t ;

    循环队列操作

    1. 创建一个空的队列 createEmptyQueue()

    2. 判断队列是否为空,空返回值是 1 ,未空是 0 isEmptyQueue () p -> rear == p -> front
    3. 判断队列是否为满 满返回值是 1 ,未满是 0 isFullQueue ()
    4. 入队 inQueue ()
    5. 出队 outQueue ()
    6. 求队列的长度 getLengthQueue ()

    2.创建一个空的队列

    queue_t * createEmptyQueue ()
    {
            queue_t * p = malloc ( sizeof ( queue_t ));
            if ( p == NULL )
            {
                    printf ( "createEmptyQueue malloc failed!!\n" );
                    return NULL ;
            }
            //只要 p->rear == p->front 就是空的队列 , 是几不重要
            //但是 p->rear p->front 的值 , 要在数组的下标范围内 0 ---- N-1
            p -> rear = p -> front = 3 ; // 3 赋值给 front, 在赋值给 rear, rear front 都得 3
            return p ;
    }

    3.判断队列是否为满 满返回1,未满返回0

    int isFullQueue ( queue_t * p )
    {
            //因为 p->rear == p->front 代表队列空 , 所以我们只能浪费一个存储位置来判断队列是否为满 ,
            //提前判断 p->reare+1 的位置是否 == p->front, 来判断是否是满队列
            return ( p -> rear + 1 ) % N == p -> front ? 1 : 0 ;
    }

    4.入队,在队列尾巴进行插入操作

    int inQueue ( queue_t * p , int x )
    {
            //0.容错判断
            if ( isFullQueue ( p ))
            {
                    printf ( "isFullQueue!!\n" );
                    return - 1 ;
            }
            //1.入队列 , rear 当做下标
            p -> a [ p -> rear ] = x ;
            //2.p->rear++,将入队的数据 x, 视为有效的元素
            p -> rear = ( p -> rear + 1 ) % N ; // %N 避免 p->rear+1 出现数组越界
            //p->rear = (p->rear+1) % N;此行代码等价于 p->rear++; p->rear =p->rear % N;
            return 0 ;
    }

    5.判断队列是否为空,空返回1, 未空返回0

    int isEmptyQueue ( queue_t * p )
    {
            return p -> rear == p -> front ? 1 : 0 ;
    }

    6. 出队列,在队列的头进行删除操作

    int outQueue ( queue_t * p )
    {
            //0.容错判断
            if ( isEmptyQueue ( p ))
            {
                    printf ( "isEmptyQueue!!\n" );
            return - 1 ;
            }
            //出队 , front 当做数组的下标
            //1.将即将出队的数据 , 临时存储到变量 x
            //因为 front 永远指向队头的元素
            int x = p -> a [ p -> front ];
            //2.让出对的元素变为无效元素
            p -> front = ( p -> front + 1 ) % N ;
            //3.将出对元素的值返回
            return x ;
    }

    7.求队列的长度

    int getLengthQueue ( queue_t * p )
    {
            //按道理 ,rear 值肯定大于 front
            //方法一
            if ( p -> rear >= p -> front )
                    return p -> rear - p -> front ;
            else // rear < front 按道理 rear 肯定大于 front 为什么 rear < front, 因为 %N, 所以 +N, 还原
                    rear的值
                    return ( p -> rear + N ) - p -> front ;
            //方法二
            //return (p->rear + N - p->front) % N;
    }
    结语
    以上就是队列的基本使用,本次代码分享到此结束,后续还会分享数据结构知识。
    最后的最后,还请大家点点赞,点点关注,谢谢大家!
  • 相关阅读:
    将Dubbo注册到Nacos,与DubboAdmin的部署
    面试官:同学,冒泡太简单了,要不手写一个【快速排序】吧...
    2023年中国BaaS行业发展概况及未来发展趋势分析:未来多链支持和发展将是BaaS平台发展重点方向[图]
    Android消息机制(Handler、Looper、MessageQueue)
    网路系统规划与设计(CCNA)复习纲要 第一部分:网络通识基础
    避免空指针
    stm32之智能小车总结
    【力扣每日一题】2023.9.11 课程表Ⅲ
    Web自动化成长之路:selenium中的PO模式
    华为认证HCIA H12-811 Datacom数通考试真题题库【带答案刷题必过】【第一部分】
  • 原文地址:https://blog.csdn.net/m0_74055118/article/details/137936255