数据结构与算法.pptx

数据结构与算法; 4 队列;1. 队列的基本概念 队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。 队首(front) ：允许进行删除的一端称为队首。 队尾(rear) ：允许进行插入的一端称为队尾。 　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。　　; 队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ，即队列的修改是依先进先出的原则进行的，如图所示。; 4 队列--顺序表示; 设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素下一个位置。 ◆ 初始化：front=rear=0。 ◆ 入队：首先将新元素插入rear所指的位置，然后队尾指针rear加1。 ◆ 出队：首先删去front所指的元素，然后将队首指针front+1，并返回被删元素。 ◆ 队列为空：front=rear。 ◆ 队满：rear=