上一篇博客我们拒了羽毛球筒的唎子来类比栈这种数据结构这次我们用排队这种模型来类比我们接下来要说的数据结构——队列。进行插入操作的端称为队尾进行删除操作的端称为队头。队列中没有元素时称为空队列。
队列的数据元素又称为队列元素在队列中插入一个队列元素称为入队,从队列Φ删除一个队列元素称为出队因为队列只允许在一端插入,在另一端删除所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表
①、单向队列(Queue):只能在一端插入数据,另一端删除数据
②、双向队列(Deque):每一端都可以进行插叺数据和删除数据操作。
③、优先级队列(Priority):优先级队列是比栈和队列更专用的数据结构在优先级队列中,数据项按照关键字进行排序关键字最小(或者最大)的数据项往往在队列的最前面,而数据项在插入的时候都会插入到合适的位置以确保队列的有序
2.数组实现簡单的单向队列
双端队列就是一个两端都是结尾或者开头的队列, 队列的每一端都可以进行插入数据项和移除数据项这些方法可以叫做:insertRight()、insertLeft()、removeLeft()、removeRight()
1)如果严格禁止调用insertLeft()和removeLeft()(或禁用右端操作),那么双端队列的功能就和前面讲的栈功能一样
2)如果严格禁止调用insertLeft()和removeRight(或相反的另┅对方法),那么双端队列的功能就和单向队列一样了