25计算机考研,数据结构知识点整理(内容借鉴了王道408+数据结构教材),还会不断完善所整理的内容,后续的内容也会不断更新(可以关注),若有错误和不足欢迎各位朋友指出!
一.队列的基本概念
队列是另一种限定性的线性表,只允许在表的一端(表尾),而在表的另一端(表头)删除元素,所以队列具有先进先出的( first in first out,FIFO)的特性,这与我们日常生活中的排队是一样的,最早进人队列的人最早离开,新来的总是加入队尾。在队列中,允许插人的一端称为队尾,允许删除的一端则称为队头(假设队列为 ,... ,,,...,),那么就是队头元素,则是队尾元素。队列中的元素按照 ,... ,,,...,顺序进人的,退出队列也必须按照同样的次序依次出队,也就是说,只有在 ,... ,,,...,都离开队列之后,才能退出队列。
抽象数据类型定义:
①InitQueue(Q)
操作前提:Q为未初始化的队列。
操作结果:将Q初始化为一个空队列。
② IsEmpty(Q)
操作前提:队列Q已经存在。
操作结果:若队列为空,则返回TRUE,否则返回FALSE。
③IsFull( Q)
操作前提:队列Q已经存在。
操作结果:若队列为满,则返回TRUE,否则返回FALSE。
④EnterQueue( Q,x)
操作前提:队列Q已经存在。
操作结果:在队列Q的队尾插入。操作成功,返回值为TRUE,否则返回值为FALSE。
⑤DeleteQueue( Q ,x )
操作结果:将队列Q的队头元素出队,并用x带回其值。操作成功,返回值为TRUE,否则返回值为FALSE。⑥ GetHead( Q ,x)
操作前提:队列Q已经存在。
操作前提:队列Q已经存在。操作结果:取队列Q的队头元素(该元素不出队),并用x带回其值。操作成功,返回值为 TRUE,否则返回值为 FALSE。⑦ ClearQueue( Q)
操作前提:队列Q已经存在。
操作结果:将队列Q置为空队列。