电子科技大学 软件技术基础 3.3f 主讲教师：刘民岷 A■ 航空航天学院 软件技术基础课程组
软件技术基础 3.3 堆栈和队列 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
2Ni VQueue 队列是一种特殊的线性表，它只允许在表的前端（front) 进行删除操作，而在表的后端（rear)进行插入操作。 进行插入操作的端称为队尾，进行删除操作的端称为队头。 队列中没有元素时，称为空队列。 ·队列具有先进先出(FFO)【 的特点。 队列空的条件：front=rear 0 队列满的条件： rear MaXSIze 出队 入队 删除 a1a2.… an 插入 front rear 电子科技大学刘民岷 堆栈和队列 2
电子科技大学 刘民岷 2 2 队列Queue 堆栈和队列 • 队列是一种特殊的线性表，它只允许在表的前端（front） 进行删除操作，而在表的后端（rear）进行插入操作。 • 进行插入操作的端称为队尾，进行删除操作的端称为队头。 • 队列中没有元素时，称为空队列。 • 队列具有先进先出（FIFO）的特点。 • 队列空的条件： front = rear • 队列满的条件： rear = MAXSIZE a1 a2 … an 入队 插入 出队 删除 front rear
2.1 V Y SETNULL(Q){置空队列：将队列初始化为空； EMPTY(Q){队列判空}：若队列为空，返回true,否则返回false: ENTER(Q,X){入队列}：在队列尾加入元素x,x成为新对尾元素； DELETE(Q){出队列：删除队列头元素； GETHEAD(Q){取头元素}：返回对头数据元素。 电子科技大学刘民岷 堆栈和队列 3
电子科技大学 刘民岷 3 2.1 队列的基本操作 堆栈和队列 • SETNULL(Q){置空队列}:将队列初始化为空； • EMPTY(Q){队列判空}:若队列为空，返回true，否则返回false; • ENTER(Q,X){入队列}:在队列尾加入元素x，x成为新对尾元素； • DELETE(Q){出队列}:删除队列头元素； • GETHEAD(Q){取头元素}:返回对头数据元素
2.2 队列的结构描述如下： 入队 define struct elemtype queue[MAXNUM+1]; /数组第一个元素是queue[O] int front; int rear; a /结构定义 rear queuetype; queuetype Q; /定义一个队列Q a1-1 ●队头指针front总是指向队头元素的 。。 前一个位置； 2 a2 ●队尾指针rear总是指向队尾元素的位 a 队头 置。 0 ●出队操作都是： Front front=front+1 出队 x queue [front ] 电子科技大学刘民岷 堆栈和队列 4
电子科技大学 刘民岷 4 2.2 队列的顺序存储结构 堆栈和队列 … ai ai-1 … a2 a1 rear 队头 Front n i 1 2 0 出队 •队列的结构描述如下： 入队 define struct {elemtype queue[MAXNUM+1]; //数组第一个元素是queue[0] int front; int rear; }queuetype; //结构定义 queuetype Q; //定义一个队列Ｑ 队头指针front总是指向队头元素的 前一个位置； 队尾指针rear总是指向队尾元素的位 置。 出队操作都是： front = front +1 ； x = queue [front ]；
2.2V 1)顺序队列的出、入对操作 (a)空队列 front rear (b)A、B、C、D、E入队 入队时，rear在变 A BC D E front rear (c)A、B、C出队 出队时，front在变 D E 电子科技大学刘民岷 front 堆栈和队ear 5
电子科技大学 刘民岷 5 2.2 队列的顺序存储结构 堆栈和队列 1）顺序队列的出、入对操作 （a）空队列 （b）A、B、C、D、E入队 （c）A、B、C出队 A B C D E front rear front rear D E front rear 入队时，rear在变 出队时，front在变