数据结构之循环队列(C++版)

时间:2022-02-11 17:42:54

#include <iostream>
#include <stdlib.h>
#include <string>
#define MAXLISTSIZE 100 //预设的存储空间最大容量

using namespace std;
typedef string ElemType;
typedef struct
{
ElemType *elem; //存储空间基址
int rear; //队尾指针
int front; //队头指针
int queuesize; //允许的最大存储空间,以元素为单位
}Queue;

void InitQueue(Queue &Q);
void DestroyQueue(Queue &Q);
void EnQueue(Queue &Q);
void DeQueue(Queue &Q);
void GetElem(Queue Q);
void QueueLength(Queue Q);
void QueueEmpty(Queue Q);
void QueueFull(Queue Q);

int main(void)
{
Queue Q;
int z;
cout << "+---------------------------+" << '\n';
cout << "|---------循环队列----------|" << '\n';
cout << "+---------------------------+" << '\n';
cout << "提示:为保证您的操作得到保存,请按正常顺序退出系统^_^" << '\n';
do
{
cout << '\n' << '\t' << '\t' << '\t' <<"--------------------------------" << '\n';
cout << '\t' << '\t' << '\t' <<"+ 主菜单 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+--------------------------------" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [1]----循环队列初始化 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [2]----循环队列的销毁 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [3]----循环队列的入队 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [4]----循环队列的出队 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [5]----循环队列的存取 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [6]----循环队列的长度 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [7]----循环队列的判空 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [8]----循环队列的判满 |" << '\n';
cout << '\t' << '\t' << '\t' <<"+ [0]----退出系统 |" << '\n';
cout << '\t' << '\t' << '\t' <<"--------------------------------" << '\n';
cout << "请输入您的选择:";
cin >> z;
switch(z)
{
case 0 : break;
case 1 : InitQueue(Q);break;
case 2 : DestroyQueue(Q);break;
case 3 : EnQueue(Q);break;
case 4 : DeQueue(Q);break;
case 5 : GetElem(Q);break;
case 6 : QueueLength(Q);break;
case 7 : QueueEmpty(Q);break;
case 8 : QueueFull(Q);break;
default:cout << "无效选项!" << '\n';system("pause");
}
}
while(z!= 0);
}

void InitQueue(Queue &Q)
{
//构造一个最大存储空间为 maxsize 的空队列 Q
int maxsize;
cout << "请输入顺序队列的最大存储空间:";
cin >> maxsize;
if(maxsize == 0)
maxsize = MAXLISTSIZE;
Q.elem = new ElemType[maxsize]; //为循环队列分配存储空间
if(!Q.elem)
{
cout << "存储分配失败" << endl; //存储分配失败
system("pause");
return;
}
Q.queuesize = maxsize;
Q.front = Q.rear = 0;
system("pause");
}//InitQueue

void DestroyQueue(Queue &Q)
{
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
delete[] Q.elem;
Q.queuesize = 0;
cout << "循环队列已销毁" << endl;
system("pause");
}

void EnQueue(Queue &Q)
{
ElemType e;
int n, j;
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
if((Q.rear + 1) % Q.queuesize == Q.front)
{
cout << "该队列已满,无法入队" << endl;
system("pause");
return;
}
cout << "请输入入队元素个数(元素个数小于等于" << Q.queuesize - ((Q.rear-Q.front+Q.queuesize) % Q.queuesize) -1 << "): " ;
cin >> n;
cout << "请输入入队的元素:";
for(j = 0; j < n; j++)
{
cin >> e;
Q.elem[Q.rear] = e;
Q.rear = (Q.rear+1) % Q.queuesize;
}
system("pause");
}

void DeQueue(Queue &Q)
{

ElemType e;
int n, j;
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
if (Q.front == Q.rear)
{
cout << "队为空,无法出队" << endl;
system("pause");
return;
}
cout << "请输入出队元素个数(元素个数小于等于" << ((Q.rear-Q.front+Q.queuesize) % Q.queuesize) << "): ";
cin >> n;
cout << "出队的元素为: ";
for(j = 0; j < n; j++)
{
e = Q.elem[Q.front];
cout << e << ' ';
Q.front = (Q.front+1) % Q.queuesize;
}
cout << endl;
system("pause");
}

void GetElem(Queue Q)
{
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
if (Q.front == Q.rear)
{
cout << "队列为空,无法获取队首元素" << endl;
system("pause");
return;
}
cout << Q.elem[Q.front] << endl;
system("pause");
}

void QueueLength(Queue Q)
{
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
cout << "循环队列的长度:" << ((Q.rear-Q.front+Q.queuesize) % Q.queuesize) << endl;
system("pause");
}

void QueueEmpty(Queue Q)
{
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
if (Q.front == Q.rear)
cout << "队列为空" << endl;
else
cout << "队列不为空" << endl;
system("pause");
return;
}

void QueueFull(Queue Q)
{
if(Q.queuesize == 0)
{
cout << "队列已销毁,请选择1初始化栈" << endl;
system("pause");
return;
}
if ((Q.rear + 1) % Q.queuesize == Q.front)
cout << "该队列已满" << endl;
else
cout << "该队列未满" << endl;
system("pause");
return;
}