功能受限的表结构:
栈:
队列:
只有两个口来进出数据,一个专门进入数据,另一个专门出数据,先进先出,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、封装线程池,数据池