day2 栈、队列

发布时间 2023-07-17 20:23:31作者: 歪爱慕外
功能受限的表结构:
    栈:
    队列:
        只有两个口来进出数据,一个专门进入数据,另一个专门出数据,先进先出,FIFO表
       
        顺序队列:
            1、存储元素的连续内存的首地址
            2、容量:
            3、队头位置:出队
            4、队尾位置:入队

            运算:创建、销毁、清空、出队、入队、对空、队满、对头、队尾、元素数量
            *需要注意的问题:
                1、存储元素是由一维数组+对头位置front+队尾位置rear来表示,入队时是队尾rear+1,出队时front+1,为了队列能够反复使用,需要把一维数组想象成一个环,因此+1后都需要对容量cal求余
                    front=(front+1)%cal;
                    rear=(rear+1)%cal;
                2、判断队空和队满的问题
                    如果不处理该问题队空、队满的条件都是front==rear,无法区分两种情况
                    ***方法1:存储元素的内存多增加一个位置空间   *(常考)
                        队空:front=rear
                        队尾:(rear+1)%cal==front
                        代价:需要额外申请存储元素的内存
                        计算数量:(rear-front+cal)%cal
                        队尾数据下标:(rear-1+cal)%cal
                    方法2:顺序队列结构中增加一个数据项,记录元素数量,通过数量与容量的对比判断队空队满(不常考)
       
        链式队列:
            由若干个节点组成的队列结构,只能操作队头节点、队尾节点
            链式队列的结构:
                1、队头指针
                2、队尾指针
                3、节点数量

                运算:创建、销毁、出队、入队、队空、队头、队尾、元素数量

        队列的应用:
            1、数据排队处理-消息排队
           *2、树的层序遍历(上->下) (左->右)
            3、图的广度优先遍历BFS
            4、封装线程池,数据池