21.2队列类模板 队列与栈不同,对数据采用“先进先出”--FIFO的管理 方式(而栈则使用“先进后出”-FILO方式)。 出队 ao a2 入队 队尾 队列数据放于作为类成员的动态数组 queue之中,在构造 函数中,将通过new来生成该动态数组,动态数组 queue的 大小由类的私有数据成员 Maxsize之值来确定。但注意,此 示例并没有循环使用上述的动态数组 queue空间。即是说 队列中至多可以存放 Maxsize个数据项,即使取走若干项后 有了空闲空间后也不可重新进行使用。若稍加改造,使存取 数据时首先通过对下标进行模 Maxsize的运算,则可实现循 环使用动态数组 queue空间的功能
21.2队列类模板 队列与栈不同，对数据采用“先进先出”--FIFO的管理 方式（而栈则使用“先进后出”--FILO方式）。 队列数据放于作为类成员的动态数组queue之中，在构造 函数中，将通过new来生成该动态数组，动态数组queue的 大小由类的私有数据成员Maxsize之值来确定。但注意，此 示例并没有循环使用上述的动态数组queue空间。即是说， 队列中至多可以存放Maxsize个数据项，即使取走若干项后 有了空闲空间后也不可重新进行使用。若稍加改造，使存取 数据时首先通过对下标进行模Maxsize的运算，则可实现循 环使用动态数组queue空间的功能。 a1 a2 …… an-1 an 队头 队尾 出队 a0 入队
#include <iostream. h> #include <process. h> template <class keytype> class Queue i int maxsize: /队列的大小 int front rear 元素放在 queue front1图到 queuerearl之中 keytype * queue;/动态数组 queue,用来存放队列数据 public: Queue( Gint size){/构造函数,生成动态数组来存放队列数据 Maxsize=size; queue=new keytype maxsize]; front=rear=-41;/意味着队列为空
#include <iostream.h> #include <process.h> template <class keytype> class Queue { int Maxsize; //队列的大小 int front,rear; //元素放在queue[front+1]到queue[rear]之中 keytype *queue; //动态数组queue，用来存放队列数据 public: Queue (int size) { //构造函数，生成动态数组来存放队列数据 Maxsize=size; queue=new keytype[Maxsize]; front=rear=-1; //意味着队列为空 };
int IsFull o i if (rear==Maxsize-1) return 1 else return o int IsEmpty o i if (front==rear) return 1 else return 0 void Add(const keytype &) keytype Delete(void)
int IsFull () { if (rear==Maxsize-1) return 1; else return 0; }; int IsEmpty () { if (front==rear) return 1; else return 0; }; void Add(const keytype &); keytype Delete(void); };
Delete在类体外定义,函数名前要加类限定符“ Queue< keytype>:” template <class keytype> keytype Queue<keytype>:: Delete(void) if (sEmptyOi cout <<" the queue is empty"<<endl exit(O); return queue ++front]; ∥/Add在类体外定义 template <class keytype> void Queue<keytype>: Add(const keytype item) i if (FuLlo) cout <<the queue is full"<<endl; else queue++rearl=item;
//Delete在类体外定义，函数名前要加类限定符“Queue<keytype>::” template <class keytype> keytype Queue<keytype>::Delete(void){ if (IsEmpty()){ cout << "the queue is empty"<<endl; exit (0); } return queue [++front]; } //Add在类体外定义 template <class keytype> void Queue<keytype>::Add(const keytype & item){ if (IsFull()) cout << "the queue is full"<<endl; else queue[++rear]=item; };
void minot int i=0; Queue<int> Qi(10); Queue<double> Qfl(10), Qf2(10 while( Qi IsFull!O){∥Qi中只能盛10个数 Qi.Add(2*i++);∥Qi中:0,2,4,6,8,10,12,14,16,18 Q1.Ad(3.0*i);∥Q中:3,6,9,12,15,18,21,24,27,30 for(i=0;i<4;i++){ /四次循环,每次总 ∥先往Qn的队列尾部加入两个数,而后又从首部删取一个数并输出 Qf2.Add(4.5 Qi. Delete( 从Q首删取一元素,乘以45,而后将其加入到Q尾部 /四次循环往QD队列尾加入:0*45,2*4.5,4*4.5,6*45 程序执行后的显示结果如下 1.5 9 3
void main() { int i=0; Queue<int> Qi(10); Queue<double> Qf1(10),Qf2(10); while (!Qi.IsFull()) { //Qi中只能盛10个数 Qi.Add(2*i++); //Qi中: 0,2,4,6,8,10,12,14,16,18 Qf1.Add(3.0*i); //Qf1中: 3,6,9,12,15,18,21,24,27,30 } for (i=0; i<4; i++){ //四次循环，每次总 //先往Qf2的队列尾部加入两个数，而后又从首部删取一个数并输出 Qf2.Add(4.5*Qi.Delete()); //从Qi首删取一元素，乘以4.5，而后将其加入到Qf2尾部 //四次循环往Qf2队列尾加入：0*4.5，2*4.5，4*4.5，6*4.5 ... } } 程序执行后的显示结果如下： 0 1.5 9 3