（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第3讲 队列

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 队列的基本概念 队列的实现方式 队列的基本操作 队列的抽象数据类型 队列的定义 1 2 3 4 1 PART ONE 先进先出 (First In First Out) 限制访问点的线性表 按照到达的顺序来释放元素。所有的插入在表的一端进行，所有的删除都在表的另一端进行 •主要元素 队头 (front) 队尾 (rear) 队列的基本概念——队列的定义 队列(Queue)：具有一定操作约束的线性表 插入和删除操作：只能在一端插入，而在另一端删除。 1 PART ONE 队列的基本概念——队列的基本操作 出队操作 判断队列是否为空 入队操作 创建队列 计算队列的长度 1 PART ONE 队列的基本概念——队列的抽象数据类型 template <class T> class Queue { public: void clear(); bool enQueue(const T item) ; bool deQueue(T & item) ; bool getFront(T & item); bool isEmpty(); bool isFull(); }; // 队列的运算集 // 变为空队列 // 将item插入队尾，成功返回真，否则假 // 返回队头元素并将其从队列中删除，成功则返回真 // 返回回队头元素，但不删除，成功则返回真 // 若队列已空返回真 // 若队列已满返回真 1 PART ONE 队列的基本概念——队列的实现方式 顺序队列 队列的顺序存储实现。 通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。 关键是如何防止假溢出 固定的存储空间 链式队列 队列的链式存储结构。 可以用一个单链表实现。插入和删除操作分别在链表的两头进行，队列中每个元素对于链表中的一个结点 可以满足大小无法估计的情况 都不允许访问队列内部元素 1 PART ONE 空队列条件： front==rear 设两个指针front，rear： rear指示队尾元素位置 front指示对头元素位置 初值front=rear=0 入队列：q[rear++]=x; 出队列：x=q[front++]; 用数组模拟普通队列 1 PART ONE （1）创建数组，对数组进行入队及出队的操作 void Push(int value) { if(rear<MaxSize) { q[rear++]=value;} } （2）入队操作，向队列中添加value const int MaxSize=100; int q[MaxSize]; int front=0; int rear=0; int pop() { if(front!=rear) {return q[front++];} } （3）出队操作，返回出队元素的值 用数组模拟普通队列 思考：如何用数组模拟计算队列的长度和判断队列是否为空？ 1 PART ONE 用数组模拟环形队列 一般情况 对满状态 front==rear 对空状态 front==rear 如何区分对满与对空呢？ 解决方案： 1.另外设一个标志以区别对空、对满 2.少用一个元素空间，约定对头指示的位置不存放元素 对空：front==rear 队满：(rear+1)%M==front M为数组长度 1 PART ONE 用数组模拟队列判断是否溢出 常规队列的几种溢出情况 （1）设数组长度为M，则 当front=0，rear=M时，再有元素入队发生溢出——真溢出 当front≠0，rear=M时，再有元素入队发生溢出——假溢出 （2）当rear指向数组的最后一个元素的时候，队列再也无法插入新元素，而这时常常还有大量的内存空间被闲置。 6 5 4 3 2 1 2 1 rear front 7 rear front 真溢出 假溢出 3 1 PART ONE 用数组模拟队列判断是否溢出 为克服假溢出——环形队列被采用 克服真溢出的解决方案： （1）队首固定，每次出队剩余元素向下移动——浪费时间 （2）假设队列长为M，让q[0]接在q[M-1]之后，如果rear+1==M,则rear=0。 实现：在rear!=front前提下（即队列不满），利用“模” 入队：q[rear]=x;rear=(rear+1)%M; 出队：x=q[