循环顺序队列(C++模板实现)
一、实验要求
<1>初始化一个队列。
<2>判断是否队空。
<3>判断是否队满。
<4>入队
<5>出队
<6>取队头元素
<7>求当前队列中元素个数
<8>编写算法实现
①初始化空循环队列;
②当键盘输入奇数时,此奇数入队;
③当键盘输入偶数时,队头出队;
④当键盘输入0时,算法退出;
⑤每当键盘输入后,输出当前队列中的所有元素。
二、数据结构设计
template<class ElementType>
class Queue{
public:
Queue(); //初始化队列
~Queue(); //销毁队列
bool empty(); //判断是否为空
bool full(); //判断栈是否为满
void enter(ElementType x); //入队
void out(); //出队
void getFront(ElementType &x);//取队头元素
int getLength(); //求当前队列中元素个数
void print(); //遍历队列
private:
ElementType * data; //数据域
int front; //首指针
int rear; //尾指针
};
三、代码实现
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <iostream>
#define MAXLEN 100
using namespace std;
template<class ElementType>
class Queue{
public:
Queue(); //初始化队列
~Queue(); //销毁队列
bool empty(); //判断是否为空
bool full(); //判断栈是否为满
void enter(ElementType x); //入队
void out(); //出队
void getFront(ElementType &x); //取队头元素
int getLength(); //求当前队列中元素个数
void print(); //遍历队列
private:
ElementType * data;
int front;
int rear;
};
//初始化队列
template<class ElementType>
Queue<ElementType>::Queue()
{
data=new ElementType[MAXLEN];
front=rear=0;
}
//销毁队列
template<class ElementType>
Queue<ElementType>::~Queue()
{
delete [] data;
}
//判断是否为空
template<class ElementType>
bool Queue<ElementType>::empty()
{
if( front==rear)
{
return true;
}
else
{
return false;
}
}
//判断栈是否为满
template<class ElementType>
bool Queue<ElementType>::full()
{
if((rear+1)%MAXLEN==front)
{
return true; //队满
}
else{
return false;
}
}
//入队
template<class ElementType>
void Queue<ElementType>::enter(ElementType x)
{
if(full())
{
cout<<"队满,不能入队!"<<endl;
}
else{
rear=(rear+1)%MAXLEN;
data[rear]=x;
}
}
//出队
template<class ElementType>
void Queue<ElementType>::out()
{
if(front==rear)
{
cout<<"队空,不能出队!"<<endl;
}
else{
front=(front+1)%MAXLEN; //指针后移
}
}
//取队头元素
template<class ElementType>
void Queue<ElementType>::getFront(ElementType &x)
{
if(empty())
{
cout<<"队空,不能取元素!"<<endl;
}
else{
x=data[(front+1)%MAXLEN];
}
}
//求当前队列中元素个数
template<class ElementType>
int Queue<ElementType>::getLength()
{
return (rear-front+MAXLEN)%MAXLEN;
}
//遍历队列
template<class ElementType>
void Queue<ElementType>::print()
{
int p=front;
while(rear!=p)
{
p=(p+1)%MAXLEN;
cout<<data[p]<<" ";
}
}
#endif // _QUEUE_H_
#include <iostream>
#include "queue.h"
#include <Cstdlib>
using namespace std;
void algorithm()
{
Queue<int> q;
int i;
cout<<"请输入一个整数:";
cin>>i;
while(i!=0)
{
if(i%2==0)
{
q.out();
cout<<"此时队列为:";
q.print();
cout<<endl;
}
else{
q.enter(i);
cout<<"此时队列为:";
q.print();
cout<<endl;
}
cout<<"请输入一个整数:";
cin>>i;
}
}
int main()
{
int i,x;
Queue<int> q;
cout<<"*******************************************"<<endl;
cout<<"0退出程序!"<<endl;
cout<<"1判断是否队空"<<endl;
cout<<"2判断是否队满"<<endl;
cout<<"3入队"<<endl;
cout<<"4出队"<<endl;
cout<<"5取队头元素"<<endl;
cout<<"6求当前队列中元素个数"<<endl;
cout<<"7输入奇数入队,偶数出队"<<endl;
cout<<"8输出队列"<<endl;
cout<<"*******************************************"<<endl;
cout<<"请输入要执行算法的序号:";
cin>>i;
while(i!=0)
{
switch(i)
{
case 1:
if(q.empty())
{
cout<<"队列为空!"<<endl;
}
else{
cout<<"队列不为空!"<<endl;
}
break;
case 2:
if(q.full())
{
cout<<"队列为满!"<<endl;
}
else{
cout<<"队列不为满!"<<endl;
}
break;
case 3:
cout<<"请输入入队元素:";
cin>>x;
q.enter(x);
break;
case 4:
q.out();
break;
case 5:
q.getFront(x);
cout<<"队头元素为:"<<x<<endl;
break;
case 6:
cout<<"队列中元素个数为:"<<q.getLength()<<endl;
break;
case 7:
algorithm();
break;
case 8:
q.print();
break;
}
system("PAUSE");
system("CLS");
cout<<"*******************************************"<<endl;
cout<<"0退出程序!"<<endl;
cout<<"1判断是否队空"<<endl;
cout<<"2判断是否队满"<<endl;
cout<<"3入队"<<endl;
cout<<"4出队"<<endl;
cout<<"5取队头元素"<<endl;
cout<<"6求当前队列中元素个数"<<endl;
cout<<"7输入奇数入队,偶数出队"<<endl;
cout<<"8输出队列"<<endl;
cout<<"*******************************************"<<endl;
cout<<"请输入要执行算法的序号:";
cin>>i;
}
return 0;
}