Circular Queue

• ## 循环队列

万次阅读 多人点赞 2018-10-31 18:25:58
循环队列出现的原因 ：顺序队列出队后 的空间不能再次利用，造成资源浪费。所以出现循环队列 这个代码是用tag标记的循环队列 思路：(rear+1)%m==front 则队列满，(front+1)%m == rear则队列空。队列开始为空，设...
循环队列出现的原因

：顺序队列出队后 的空间不能再次利用，造成资源浪费。所以出现循环队列

这个代码是用tag标记的循环队列

思路：(rear+1)%m==front 则队列满，(front+1)%m == rear则队列空。队列开始为空，设tag=0。

简单的说就是front 追 rear 如果追上就是空队列

然后rear如果追上front 就是满队列

当 tag == 1且 front == rear 时队满

当tag == 0 且front == rear 时队空

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef char QElemType;
#define MAXQSIZE		10
typedef struct {
QElemType *elem;
int tag;
int front;
int rear;
}CircleQueue;
int InitCircle(CircleQueue &Q)
{
Q.elem = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
Q.front = 0;
Q.rear = 0;
Q.tag = 0;
return 1;
}
int ClearCircleQueue(CircleQueue &Q) //清空
{
Q.front = 0;
Q.rear = 0;
Q.tag = 0;
return 0;
}
int DestoryCircleQueue(CircleQueue &Q)//销毁
{
free(Q.elem);
Q.elem = NULL;
return 1;
}
int CircleQueueLength(CircleQueue Q)//判断长度
{
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

int EmptyCircle(CircleQueue Q) //判空
{
if(Q.rear == Q.front && Q.tag == 0)
return 1;
return 0;
}
int EnQueue(CircleQueue &Q, QElemType e) //入队
{
if(Q.tag == 1)
return 0;
Q.elem[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
if(Q.rear == Q.front)
Q.tag = 1;
return 1;
}
int DeQueue(CircleQueue &Q, QElemType &e)//出队
{
if(Q.rear == Q.front && Q.tag == 0)
return 0;
e = Q.elem[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
if(Q.front == Q.rear)
Q.tag = 0;
return 1;
}

int ShowCircleQueue(CircleQueue Q)//显示
{
if(Q.rear == Q.front && Q.tag == 0)
{
return 0;
}
while(1)
{
printf("%c ", Q.elem[Q.front]);
Q.front = (Q.front + 1) % MAXQSIZE;
if(Q.front == Q.rear)
break ;
}
return 1;
}

void help()
{

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;
}

int main ()
{
CircleQueue Q;
help();
int operate_code;
char e;
while(1)
{
cin>>operate_code;
if(operate_code == 1)
{
InitCircle(Q);
}
if(operate_code == 2)
{
ClearCircleQueue(Q);
}
if(operate_code == 3)
{
DestoryCircleQueue(Q);
}
if(operate_code == 4)
{
int len = CircleQueueLength(Q);
cout<<"队列的长度为 = " << len;
}
if(operate_code == 5)
{
if( EmptyCircle(Q) )
printf("队列为空\n");
else
printf("队列非空\n");
}

if(operate_code == 6)
{
cout << "请输入你要入队的元素: " << endl;
cin >> e;
if(EnQueue(Q, e))
{
cout << "入队成功" << endl;
}
else
{
cout << "入队失败" << endl;
}
}
if(operate_code == 7)
{
if(	DeQueue(Q, e))
{
cout << "出队成功,队首元素为 = " << e << endl;
}
else
cout << "队列为空，队内无元素 "<<endl;

}
if(operate_code == 8)
{
ShowCircleQueue( Q);
}
if(operate_code <= 0)
break;
}
return 0;
}



展开全文
• ——————简单实现了插入，删除，长度，退出等功能——————
循环队列源代码（C语言版）

/*******简单实现了插入，删除，长度，退出等功能********/

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//定义队列结构
typedef struct Queue{
int * base;
int front;
int rear;
}SQueue;
//初始化100个数字的队列
void InitQueue(SQueue * Q){
Q->base=(int *)malloc(MAXSIZE*sizeof(int));
Q->front=Q->rear=0;
}
//返回队列长度
void QueueLength(SQueue * Q){
printf("此队列的长度为：%d\n",(Q->rear-Q->front+MAXSIZE)%MAXSIZE);
}

//插入节点
void InsertQueue(SQueue * Q,int e){
if((Q->rear+1)%MAXSIZE==Q->front)
printf("队列已满！\n");
else
{
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXSIZE;
}

}
//删除节点
DeleteQueue(SQueue * Q){
if(Q->rear==Q->front)
printf("队列已空！\n");
else{
Q->front=(Q->front+1)%MAXSIZE;
printf("删除完成！\n");
}
}
//打印队列
void PrintQueue(SQueue Q){
printf("________________________________________________________\n");
while(Q.front!=Q.rear){    //此处留了一个标志位，所以不用再打印最后一个数。
printf("%d ",Q.base[Q.front]);
Q.front=(Q.front+1)%MAXSIZE;
}
printf("\n————————————————————————————\n");
}
//主函数
int main(){

SQueue M;int i,x,v;
InitQueue(&M);
for(i=1;i<=12;i++){
InsertQueue(&M,i);
}
printf("十二个数字的队列已经建立完成！\n");
PrintQueue(M);
printf("请输入序号进行操作：1.插入  2.删除  3.长度  4.退出\n");
scanf("%d",&x);
while(x!=0){
switch(x){
case 1:printf("请输入要插入的值：");
scanf("%d",&v);
InsertQueue(&M,v);
PrintQueue(M);
break;
case 2:DeleteQueue(&M);
PrintQueue(M);
break;
case 3:printf("正在计算长度......\n");
QueueLength(&M);
break;
case 4:exit(0);
default:printf("输入有误，请重新输入！\n");
}
printf("请输入序号进行操作：1.插入  2.删除  3.长度  4.退出\n");
scanf("%d",&x);
}
return 0;
}

程序截图：

联系邮箱：xhsgg12302@outlook.com

2016_12_28


展开全文

...