队列

1.空间浪费:顺序队列前面的空闲空间无法再被使用、2.“假溢出”:当顺序队列移动至顺序表尾部时，即便顺序表中有空闲空间，新元素也无法成功入队。

队列

• 定义：队列也是一种操作受限的线性表只允许在一端插入，在另一端删除
• 说明
  • 入队(进队):向队列中插入元素的操作
  • 出队(离队):从队列中删除元素的操作
  • 队头(首):允许删除的一端
  • 队尾:允许插入的一端
  • 空队列:没有元素的队列
• 特点：队列具有先进先出(First In First Out，FIFO)的特性
• 基本操作
  • ①InitQueue(Q):初始化一个空队列 Q。
  • ②EnQueue(Qx):在队列Q的尾部插入一个新的元素x。
  • ③ DelQueue(Q,*y):删除队列Q的队头的元素，并存入*y中。
  • ④QucueEmpty(Q):判队列Q是否为空。若为空返回一个真值，否则返回一个假值。
  • ⑤GetFront(Q,*y):取得队列Q的队头元素。该运算与DelQueue(Q,*y)不同，后者要修改队头元素指针
• 队列的顺序存储
  • 定义：分配一块连续的存储单位存放队列中的元素
  • 缺点：
    • 1.空间浪费:顺序队列前面的空闲空间无法再被使用
    • 2.“假溢出”:当顺序队列移动至顺序表尾部时，即便顺序表中有空闲空间，新元素也无法成功入队。
• 队列的循环结构
  • 注意：对干循环队列必须给定最大值MAXOSIZE =入队:rear=(rear+1)%数组长度;出队:循环递增front值
  • 区分队空和队满： 方法1:另设一个标志位以区别队列是空还是满; 方法2:约定 队空条件:Sq.front ==Sq.rear 队满条件:队尾指针加1等于队头指针，即 f (Sq.rear+1) %MAXSIZE==Sq.front 即一个大小为MAXSIZE的循环队列最多有MAXSIZE-1个元素
• 队列的链式结构
  • 定义:队列的链式表示称为链队列
  • 说明
    • 本质是一个同时带有队头指针、队尾指针的单链表
    • 头指针指向队头结点
    • 尾指针指向队尾指针