队列的基本概念.ppt

* 3.3 队列一、队列的基本概念 １、队列定义 ３、存储结构 ４、运算规则 ５、实现方式 ２、逻辑结构 只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。 队尾插入 队头删除 与线性表相同，仍为一对一关系。 顺序队列或链队列，以循环顺序队列更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作：入队或出队，建空队列，判队空或队满等操作。 * 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 在队尾插入元素称为入队；在队首删除元素称为出队。 当队列中没有数据元素时称为空队列。 队首 队尾 * 二、队列抽象数据类型 数据集合：{a0,a1,…,ai ,…,an-1｝ ai的数据类型为 DataType 操作集合：(1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列 (4)QueueDelete(Q,d) 出队列 (5)QueueGet(Q,d) 取队头数据元素 等 * 三、顺序队列 1、顺序队列　　　采用顺序存储结构的队列。 2、顺序队列的存储结构 　　它利用一个一维数组来 存储数据元素，另再设立一 个队头指示器和一个队尾指 示器分别指向当前队头元素 和当前队尾元素。用C语言 定义为： typedef struct { DataType queue[MaxQueueSize]; int rear; int front; }SeqCQueue; a1 a2 a3 data a4 ８ ７ ６ ５ ４ ３ ２ １ ０ front rear (队尾) (队头) * 具体算法： void QueueInitiate(SeqCQueue *Q) /*初始化顺序循环队列Q*/ { Q-rear = 0; /*定义初始队尾指针下标值*/ Q-front = 0; /*定义初始队头指针下标值*/ Q-count = 0; /*定义初始计数器值*/ } * 算法说明：向循环队列的队尾插入一个元素 分 析： (1) 插入前应当先判断队列是否满？ if (Q-count0 Q-rear==Q-front) return 0; (2）插入动作 Q-queue[Q-rear] = x; Q-rear = (Q-rear + 1) % MaxQueueSize; Q-count++; return 1; 2） 入队操作 队列尺寸 * int QueueAppend(SeqCQueue *Q, DataType x) { if(Q-count 0 Q-rear == Q-front) { printf(队列已满无法插入! \n); return 0; } else { Q-queue[Q-rear] = x; Q-rear = (Q-rear + 1) % MaxQueueSize; Q-count++; return 1; } } 入队操作完整算法 * 3）出队操作 算法说明：删除队头元素，返回其值 e 分 析： （1） 在删除前应当判断队列是否空？ if(Q-count == 0) return 0; （2）删除动作 m = Q-queue[Q-front]; Q-front = (Q-front + 1) % MaxQueueSize; Q-count--; front指针在元素出队后再加 * int QueueDelete(SeqCQueue *Q, DataType *d) { if(Q-count == 0) { printf(队列已空无数据元素出队列! \n); return 0; } else { *d = Q-queue[Q-front]; Q-front = (Q-front + 1)