数据结构与算法-队列

队列2/25队列队列基本概念队列的表示和实现循环队列队列的应用3/25队列类似于排队，新加入的元素放到它的尾端，在它的前段移去数据。和栈不同，队列是一种使用两端的结构：一端用来加入新元素，另一端用来移去元素。排队买票队列队列的定义队列(queue)：插入和删除在不同端进行的线性表。队尾(rear)：添加新元素的一端。队首(front)：删除元素的一端。时间有序表：先进先出（FIFO）特征的线性结构。a0，a1，a2，…，an-1，进队出队队首队尾5/25队列操作clear（）—

清空队列。isEmpty（）—

判断队列是否为空。enqueue（el）—

队列的尾部加入元素el。dequeue（）—

取出队列的第一个元素。firstEl（）—

返回队列的第一个元素，但不移去它。6/25队列的顺序表示1用数组queue[MaxSize]描述一个队列，

location(i)=i-1;frontrear队空：front=0;rear=-1;frontrearA插入A元素：front=0;rear=0;frontrearAB插入B元素：front=0;rear=1;7/25队列的顺序表示1frontrearABCD队列满：rear=MaxSize-1frontrearBCD出队，front=1;frontrearBCD插入E：rear=MaxSize-1;队列满，不能插入此空间浪费了！8/25队列的顺序表示1frontrearABCD队列满：rear=MaxSize-1frontrearBCD出队，front=1;frontrearBCD出队后调整：front=0;rear=rear-1;9/25队列的顺序存储结构用一组地址连续的存储单元依次存放从队头到队尾的元素。front=-1rear=-1123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题(设数组大小为M)，则：当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出。当front-1,rear=M-1时，再有元素入队发生溢出——假溢出。10/25队列溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间。循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];0M-11frontrear…...…...11/25J4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front012345rearfront队空：front==rear队满：front==rear12/25循环队列frontrear队列空：front=rear;frontrearBCD队列满：(rear+1)%MaxSize==front13/25循环队列frontrearBCD队列满：frontrearCD出队：front=(front+1)%MaxSize进队：rear=(rear+1)%MaxSizefrontrearCDE14/25队列中结点的个数队中结点的个数：(rear-front+maxSize)%maxSize15/25队列的链接表示·链接队列：front和rear分别是队首和队尾指针。datalink队首结点∧front队尾结点rear16/25链式队列的操作队首结点∧队尾结点rearfront队尾结点(队首结点)rear∧front空队列：front=rear=NULL链式队列的结点类定义·结点类与自定义链表堆栈中所使用的相同。template<classT>classLinkedQueue;template<classT>classNode{friendLinkedQueue<T>;private:

Tdata;Node<T>*link;

};datalinkfrontrear链式队列的类定义·链接表示的队列：front、rear分别是队列的队首和对尾指针。∧frontreartemplate<classT>classLinkedQueue{public:

LinkedQueue(){front=rear=0;}

～Queue();

boolIsEmpty(){return((front)?false:true);}boolIsFull();TFirst();TLast();LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Del(T&x);private:Node<T>*front;Node<T>*rear;};∧front初始化∧rear链式队列的进队操作·链接表示的队列：入队操作，front、rear分别是队列的队首和队尾指针。template<classT>

LinkedQueue&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=0;if(front)//队列不为空

rear->link=p;

else//队列为空

front=p;rear=p;return*this;}链式队列的出队操作·链接表示的队列：出队操作，front、rear分别是队列的队首和对尾指针。template<classT>

LinkedQueue&LinkedQueue<T>::Del(){if(IsEmpty()){cout<<“outofbounds”;return*this;}

x=front->data;Node<T>*p=front;front=front->link;deletep;return*this;}21/25队列的应用打印多项式(a+b)i的系数:1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1i=12345622/2