3.7 队列的表示和实现

3.5 队列的表示和操作实现

• 相关术语
  • 队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。
  • 表尾及a ( ( ( ( (n)))))端，称为队尾；表头即a ( ( ( ( (1)))))端称为队头
  • 它是一种先进先出（FIFO）的线性表
    插入的元素称为入队；删除的元素称为出队
    队列的存储结构分为链队或者顺序队
• 队列的相关概念
  1. 定义：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）
  2. 逻辑结构：与同线性表相同，仍为一对一关系
  3. 存储结构：顺序队或者链队，以循环顺序队列更常见。
  4. 运算规则：只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则
  5. 实现方式：关键时掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。

3.5.1 队列的抽象数据类型定义

ADT  Queue{
  	数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n>=0}
  	数据关系：R1={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}
  	基本操作：
      	InitQueue(&Q)
      			操作结果：构造一个空的队列
      	DestoryQueue(&Q)
      			初始条件：队列Q已经存在
      			操作结果：队列Q被销毁，不再存在
     	  ClearQueue(&Q)
      			初始条件：队列Q已经存在
      			操作结果：将队列Q清为空队列
      	QueueLength(Q)
      			初始条件：队列Q已经存在
      			操作结果：返回Q的元素个数，即队列长度。
       QueueEmpty(Q)
      			初始条件：队列Q已经存在
      			操作结果：若Q为空队列，则返回TURE，否则返回FALSE
      	GetHead(Q,&e)
      			初始条件：队列Q已经存在，且非空
      			操作结果：用e返回Q的队首元素
      	EnQueue(&Q,e)
      			初始条件：队列Q已经存在,Q空间未满
      			操作结果：插入元素e为Q的新元素
      	DeQueue(&Q,&e)
      			初始条件：Q为非空队列
      			操作结果：删除Q的队头元素，并用e返回其值。
}ADT Queue