#include<iostream>
using namespace std;
#define QUEUE_INIT_SIZE 5 //队列存储空间的初始分配量
#define QUEUE_INCREMENT 5 //队列存储空间的分配增量
#define QUEUE_FREESIZE 10 //队列存储空间的回收预定值
#define PERCENT 0.5 //队列闲置空间的回收比例
#define Elemtype int
class SeqQueue{
private:
Elemtype *element;
int QueueSize;
int front;
int rear;
public:
bool InitQueue();
bool InsertSeqQueue(Elemtype e);
bool DeleteQueue(Elemtype &e);
bool QueueEmpty();
bool QueueFull();
Elemtype getQueueHead();
Elemtype getQueueLast();
void ClearQueue();
void ShowQueue();
};
bool SeqQueue::QueueEmpty()
//测队空
{
if(front == rear)
return true;
else
return false;
}
bool SeqQueue::QueueFull()
//测队满
{
if ((rear+1)%QueueSize==front)
return true;
else
return false;
};
Elemtype SeqQueue::getQueueHead()
//获取队头元素
{
Elemtype x;
if
(front==rear)
throw"队列是空的,无队头元素";
x=element[front];
return x;
}
Elemtype SeqQueue::getQueueLast()
//获取队尾元素
{
Elemtype x;
if
(front==rear)
throw"队列是空的,无队尾元素";
x=element[rear-1];
return x;
}
void SeqQueue::ClearQueue()
//清空队列
{
front=rear=0;
cout<<"队列已空\n";
};
void SeqQueue::ShowQueue()
//展示队列
{
int i=front;
while(i!=rear)
{
cout<<element[i]<<'\t';
i=(i+1)%QueueSize;
}
cout<<endl;
};
bool SeqQueue::InitQueue()
//建立队列
{
element = new Elemtype[QUEUE_INIT_SIZE];
if
(!element)
return false;
QueueSize = QUEUE_INIT_SIZE;
front =0;
rear = 0;
}
bool SeqQueue::InsertSeqQueue(Elemtype e)
//元素入队
{
int newfront , newrear;
Elemtype e1;
if
((rear + 1) % QueueSize == front)
{
Elemtype *data = new Elemtype[QueueSize + QUEUE_INCREMENT];
if (!data)
return false;
newfront = front;
newrear = front;
QueueSize = QueueSize + QUEUE_INCREMENT;
while (DeleteQueue(e1))
{
newrear = (newrear + 1) % QueueSize;
data[newrear] = e1;
}
delete[]element;
element = data;
rear = newrear;
front = newfront;
}
rear = (rear + 1) % QueueSize;
element[rear] =e;
return true;
}
bool SeqQueue::DeleteQueue(Elemtype &e)
//元素出队
{
int i,j,num;
int length=(rear-front+QueueSize)%QueueSize;
int back=int(QUEUE_FREESIZE*PERCENT);
//回收个数为限定值 QUEUE_FREESIZE 的 50%
Elemtype *newelement;
if(rear==front)
return false;
//队列为空则报告错误并退出程序
e=element[front];
front=(front+1)%QueueSize;
if
(QueueSize-length>=QUEUE_FREESIZE)
//判断闲置空间是否达到定值
{
if (front>rear)
//判断队头指针与队尾指针的相对位置
{
for(i=QueueSize-back-1,j=QueueSize-1;j>= front;i--,j--)
element[i]=element[j];
//移动 front 开始到 QueueSize 结束的 num 个元素
num=QueueSize-front;
front =QueueSize-back-num;
}
else
if(QueueSize-(rear+1)<back)
//判断队尾指针后的闲置空间是否不够回收
{
for(i=0,j=front;j<=rear;i++,j++)
element[i]=element[j];
//移动所有元素的位置
front=0;
//令队头指针指向队列首位置
rear=front+length;
//队尾指针指向最后一个元素的后一个位置
}
newelement=(Elemtype *)realloc(element,(QueueSize-back)*sizeof(Elemtype));
//回收空闲空间
if
(! newelement)
return false;
//内存分配失败 , 报告错误并退出程序
element=newelement;
QueueSize=QueueSize-back;
//修改存储空间的大小
}
}
int main()
{
int choice;
do
//显示主菜单
{
cout<<"****************欢迎使用循环队列存储空间动态回收系统********************"<<endl;
cout<<endl;
cout<<"1.新建队列\n";
cout<<"2.元素入队\n";
cout<<"3.元素出队\n";
cout<<"4.测队空\n";
cout<<"5.测队满\n";
cout<<"6.取队头元素\n";
cout<<"7.取队尾元素\n";
cout<<"8.清空队列\n";
cout<<"9.退出系统\n";
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"请选择:";
cin>>choice;
switch(choice)
{
case 1:
//新建队列
SeqQueue Q;
Elemtype e;
cout<<"队列已建立!\n"<<endl;
break;
case 2:
//元素入队
cout<<"请输入队列元素:";
cin>>e;
cout<<endl;
Q.InsertSeqQueue(e);
cout<<"入队成功!\n"<<endl;
system("pause");
break;
case 3:
//元素出队
try
{
e=Q.DeleteQueue(e);
cout<<"出队元素为:"<<e<<endl;
}
catch(char *el)
{
cout<<el<<endl;
}
system("pause");
break;
case 4:
//测队空
if
(Q.QueueEmpty())
cout<<"队列是空的\n";
else
cout<<"队列不为空\n";
system("pause");
break;
case 5:
//测队满
if
(Q.QueueFull())
cout<<"队列是满的\n";
else
cout<<"队列不是满的\n";
system("pause");
break;
case 6:
//取队头元素
try
{
e=Q.getQueueHead();
cout<<"队头元素为:"<<e<<endl;
}
catch (char *em)
{
cout<<em<<endl;
}
system("pause");
break;
case 7:
//取队尾元素
try
{
e=Q.getQueueLast();
cout<<"队尾元素为:"<<e<<endl;
}
catch(char *en)
{
cout<<en<<endl;
}
system("pause");
break;
case 8:
//清空队列
Q.ClearQueue();
cout<<"队列已清空!\n"<<endl;
system("pause");
break;
case 9:
//退出系统
break;
}
}
while(choice!=9);
return 0;
}
using namespace std;
#define QUEUE_INIT_SIZE 5 //队列存储空间的初始分配量
#define QUEUE_INCREMENT 5 //队列存储空间的分配增量
#define QUEUE_FREESIZE 10 //队列存储空间的回收预定值
#define PERCENT 0.5 //队列闲置空间的回收比例
#define Elemtype int
class SeqQueue{
private:
Elemtype *element;
int QueueSize;
int front;
int rear;
public:
bool InitQueue();
bool InsertSeqQueue(Elemtype e);
bool DeleteQueue(Elemtype &e);
bool QueueEmpty();
bool QueueFull();
Elemtype getQueueHead();
Elemtype getQueueLast();
void ClearQueue();
void ShowQueue();
};
bool SeqQueue::QueueEmpty()
//测队空
{
if(front == rear)
return true;
else
return false;
}
bool SeqQueue::QueueFull()
//测队满
{
if ((rear+1)%QueueSize==front)
return true;
else
return false;
};
Elemtype SeqQueue::getQueueHead()
//获取队头元素
{
Elemtype x;
if
(front==rear)
throw"队列是空的,无队头元素";
x=element[front];
return x;
}
Elemtype SeqQueue::getQueueLast()
//获取队尾元素
{
Elemtype x;
if
(front==rear)
throw"队列是空的,无队尾元素";
x=element[rear-1];
return x;
}
void SeqQueue::ClearQueue()
//清空队列
{
front=rear=0;
cout<<"队列已空\n";
};
void SeqQueue::ShowQueue()
//展示队列
{
int i=front;
while(i!=rear)
{
cout<<element[i]<<'\t';
i=(i+1)%QueueSize;
}
cout<<endl;
};
bool SeqQueue::InitQueue()
//建立队列
{
element = new Elemtype[QUEUE_INIT_SIZE];
if
(!element)
return false;
QueueSize = QUEUE_INIT_SIZE;
front =0;
rear = 0;
}
bool SeqQueue::InsertSeqQueue(Elemtype e)
//元素入队
{
int newfront , newrear;
Elemtype e1;
if
((rear + 1) % QueueSize == front)
{
Elemtype *data = new Elemtype[QueueSize + QUEUE_INCREMENT];
if (!data)
return false;
newfront = front;
newrear = front;
QueueSize = QueueSize + QUEUE_INCREMENT;
while (DeleteQueue(e1))
{
newrear = (newrear + 1) % QueueSize;
data[newrear] = e1;
}
delete[]element;
element = data;
rear = newrear;
front = newfront;
}
rear = (rear + 1) % QueueSize;
element[rear] =e;
return true;
}
bool SeqQueue::DeleteQueue(Elemtype &e)
//元素出队
{
int i,j,num;
int length=(rear-front+QueueSize)%QueueSize;
int back=int(QUEUE_FREESIZE*PERCENT);
//回收个数为限定值 QUEUE_FREESIZE 的 50%
Elemtype *newelement;
if(rear==front)
return false;
//队列为空则报告错误并退出程序
e=element[front];
front=(front+1)%QueueSize;
if
(QueueSize-length>=QUEUE_FREESIZE)
//判断闲置空间是否达到定值
{
if (front>rear)
//判断队头指针与队尾指针的相对位置
{
for(i=QueueSize-back-1,j=QueueSize-1;j>= front;i--,j--)
element[i]=element[j];
//移动 front 开始到 QueueSize 结束的 num 个元素
num=QueueSize-front;
front =QueueSize-back-num;
}
else
if(QueueSize-(rear+1)<back)
//判断队尾指针后的闲置空间是否不够回收
{
for(i=0,j=front;j<=rear;i++,j++)
element[i]=element[j];
//移动所有元素的位置
front=0;
//令队头指针指向队列首位置
rear=front+length;
//队尾指针指向最后一个元素的后一个位置
}
newelement=(Elemtype *)realloc(element,(QueueSize-back)*sizeof(Elemtype));
//回收空闲空间
if
(! newelement)
return false;
//内存分配失败 , 报告错误并退出程序
element=newelement;
QueueSize=QueueSize-back;
//修改存储空间的大小
}
}
int main()
{
int choice;
do
//显示主菜单
{
cout<<"****************欢迎使用循环队列存储空间动态回收系统********************"<<endl;
cout<<endl;
cout<<"1.新建队列\n";
cout<<"2.元素入队\n";
cout<<"3.元素出队\n";
cout<<"4.测队空\n";
cout<<"5.测队满\n";
cout<<"6.取队头元素\n";
cout<<"7.取队尾元素\n";
cout<<"8.清空队列\n";
cout<<"9.退出系统\n";
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"*******************************************************************"<<endl;
cout<<"请选择:";
cin>>choice;
switch(choice)
{
case 1:
//新建队列
SeqQueue Q;
Elemtype e;
cout<<"队列已建立!\n"<<endl;
break;
case 2:
//元素入队
cout<<"请输入队列元素:";
cin>>e;
cout<<endl;
Q.InsertSeqQueue(e);
cout<<"入队成功!\n"<<endl;
system("pause");
break;
case 3:
//元素出队
try
{
e=Q.DeleteQueue(e);
cout<<"出队元素为:"<<e<<endl;
}
catch(char *el)
{
cout<<el<<endl;
}
system("pause");
break;
case 4:
//测队空
if
(Q.QueueEmpty())
cout<<"队列是空的\n";
else
cout<<"队列不为空\n";
system("pause");
break;
case 5:
//测队满
if
(Q.QueueFull())
cout<<"队列是满的\n";
else
cout<<"队列不是满的\n";
system("pause");
break;
case 6:
//取队头元素
try
{
e=Q.getQueueHead();
cout<<"队头元素为:"<<e<<endl;
}
catch (char *em)
{
cout<<em<<endl;
}
system("pause");
break;
case 7:
//取队尾元素
try
{
e=Q.getQueueLast();
cout<<"队尾元素为:"<<e<<endl;
}
catch(char *en)
{
cout<<en<<endl;
}
system("pause");
break;
case 8:
//清空队列
Q.ClearQueue();
cout<<"队列已清空!\n"<<endl;
system("pause");
break;
case 9:
//退出系统
break;
}
}
while(choice!=9);
return 0;
}