C++数据结构--循环队列的实现

╰+攻爆jí腚メ 2021-12-09 08:10 406阅读 0赞

**1.循环队列模型与数组视图的对照  
![20130729134211421][]  
  
  
  
  
  
  
2.实现代码：  
const int MAX=3; //循环队列的固定长度   
  
  
template<typename T>  
class myQue  
\{   
private:  
T que\[MAX\];  
size\_t front\_index; //队首下标   
size\_t back\_index; //队尾下标  
size\_t length;  //队列长度  
public:  
myQue():front\_index(0),back\_index(0),length(0) //初始化队列   
\{   
\}  
  
void pop()  //岀队   
\{   
if(empty())  
\{   
cerr<<"error,the queue is empty."<<endl;  
return;  
\}  
que\[front\_index\]=T(); //把队首元素置空   
front\_index=(front\_index+1)%MAX ; //计算队首下标的位置   
length--;   
  
\}  
  
void push(const T& val)  //入队   
\{   
if(full())  
\{   
cerr<<"error,the queue is full."<<endl;  
return;  
\}  
que\[back\_index\]=val;  
back\_index=(back\_index+1)%MAX ; //计算队尾下标的位置   
length++;  
\}  
  
T& front() //返回队首元素   
\{   
return que\[front\_index\];  
\}  
  
size\_t size() //返回队列大小   
\{   
return length;;  
\}  
  
bool empty()  //判断队列是否为空   
\{   
return length==0;  
\}  
  
bool full() //判断队列是否为满  
\{   
return length==MAX;   
\}   
  
\};  
  
  
template<typename T>  
//打印队列所有元素  
void print(myQue<T> mq)  
\{   
while(!mq.empty())  
\{   
cout<<mq.front()<<ends;  
mq.pop();  
\}  
\}  
  
  
int main()  
\{   
 myQue<int> mq;  
 mq.pop(); //error,the queue is empty.  
 mq.push(1);  
 mq.push(2);  
 mq.push(3);  
 mq.push(4); //error,the queue is full.  
 cout<<mq.size()<<endl; //3  
 print(mq); //1 2 3  
 cout<<endl<<endl;  
  
 mq.pop();  
 cout<<mq.size()<<endl; //2  
 mq.push(4);  
 print(mq); //2 3 4  
  
\}  
  
  
运行结果：**

**![Center][]**

**另附队列的设配器类**

**template<typename T>  
class myQue  
\{  
private:  
list<T> que;  
public:  
void pop()  
\{  
que.pop\_front();  
\}  
  
void push(T val)  
\{  
que.push\_back(val);  
\}  
  
T& front()  
\{  
return que.front();  
\}  
  
size\_t size()  
\{  
return que.size();  
\}  
  
bool empty()  
\{  
return que.empty();  
\}  
  
\};  
  
  
template<typename T>  
void print(myQue<T> mq)  
\{  
while(!mq.empty())  
\{  
cout<<mq.front()<<ends;  
mq.pop();  
\}  
\}  
  
  
int main()  
\{  
myQue<int> mq;  
mq.push(1);  
mq.push(2);  
mq.push(3);  
cout<<mq.size()<<endl; //3  
 print(mq); //1 2 3  
 cout<<endl;  
  
 mq.pop();  
 cout<<mq.size()<<endl; //2  
 print(mq); //2 3  
  
\}**

[20130729134211421]: /images/20211208/904715ff62fa45e6be94f2f05cfc1fe5.png
[Center]: /images/20211208/53d39855e8684f79bc496b9c2f090d6c.png