利用C++搭建的循环顺序队列

大家好，欢迎来到IT知识分享网。

利用C++搭建的循环顺序队列

在操作系统中的作业调度中有一个比较典型的调度策略，就是先来先服务的策略。当多个作业请求需要进行系统执行调用时，先提出服务请求的作业会被率先执行，后提出服务请求的会按照提出请求的顺序“依次排队”，等候后续的执行。其实这一排队策略就可以借助队列来予以实现。

1.队列的简要概述

队列一种限定存取位置的线性表，操作方式为：在表的一段输入，在表的另一端删除与取出。允许插入的一段叫做队尾(rear)，允许删除和取出的一端叫做队头（frout）。具体的操作形式，如下图所示：

这个操作是不是让大家想到了去火车站买票的操作。队列最大的特征就是：先进先出FIFO（First In First Out）。

队列的存储方式有两种:一种是基于数组的存储方式，即顺序队列;另一种是基于链表的存储方式。本文是利用C++搭建的顺序队列。

2.搭建思路

2.1队列基本的操作—插入与删除/读取

队列的插入与删除代表了队列的基本内容，也是队列的核心内容。队列的插入与删除/读取的操作如下图示：

从图中可以看出：

2.2队列基本操作的讨论

借助2.1的基本操作，我们可以构建出一个循环队列，那在进行基本操作过程中，还需要什么值得注意的呢？

3.代码

下列代码就是根据上述思路所搭建的，供大家参考。

#include<iostream> using namespace std; /队列结构定义*/ template<typename Datatype> class Queue { public: Queue(int size) { Maxsize = size; //初始化最大容量 //初始化队首、队尾、和元素数位0 Frout = 0; Rear = 0; count = 0; Elements = new Datatype[size]; //分配空间 //如果空间分配失败，则进行退出 if (Elements==NULL) { cout << "空间分配失败"<< endl; exit(1); } } ~Queue() { delete [] Elements; } //入队操作 bool insert(Datatype data); //出队操作 Datatype delElement(); private: int count; //队列的个数 int Maxsize; //队列的最大元素 int Frout; //队首 int Rear; //队尾 Datatype *Elements; //数据指针 }; /入队操作*/ template<typename Datatype> bool Queue<Datatype>::insert(Datatype data) { if (((Rear+1)%Maxsize)==Frout) //判断是否队列已满 { cout << "当前队列已满" << endl; return false; } Elements[Rear] = data; //将数据插入队尾 Rear = (Rear + 1)%Maxsize; count++; //元素数+1 } /出队操作*/ template<typename Datatype> Datatype Queue<Datatype>::delElement() { if (Rear== Frout) //判断当前是否为队空 { cout << "当前队列为空队列" << endl; exit(1); } Datatype Data = Elements[Frout]; //去除队首元素 Frout = (Frout + 1)%Maxsize; //设置新的队首位置，为节省空间，采用取模法 count--; //队内元素减1 return Data; } /主函数*/ int main() { //输入构建队列的长度 cout << "输入构建队列的长度" << endl; int Queue_Number; cin >> Queue_Number; Queue<int> queue(Queue_Number); //初始化循环队列 for (int i = 0; i < (Queue_Number-1); i++) { queue.insert(i*10); } queue.insert(100); cout << "构建的队列依次取出为" << endl; for (int i = 0; i < (Queue_Number - 1); i++) { cout<<queue.delElement()<<" "; } cout << ""<<endl; cout << "" << endl; cout << queue.delElement() << " "; return 0; } 

上述程序我已经运行过了，我认为没有什么问题。如果大家在参考的过程中，遇到什么问题，也希望大家相互交流。