循环队列的基本操作

2024-07-17 22:56| 来源: 网络整理| 查看: 265

循环队列的基本操作一、循环队列二、循环队列的理解二、循环队列的算法①、循环队列--队列的顺序存储结构②、构造空循环队列③、入队④、出队⑤、返回Q元素的个数,即队列的长度⑥、遍历应用Queue.hQueue.c运行结果

一、循环队列

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。

二、循环队列的理解

例：设有循环队列QU[0，5]，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图所示。在这里插入图片描述入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过front=rear来判断队列“空”还是“满”。 ☞☞解决此问题的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即： ◆ rear所指的单元始终为空。 ◆ 循环队列为空：front=rear 。 ◆ 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

二、循环队列的算法 ①、循环队列–队列的顺序存储结构 /******循环队列--队列的顺序存储结构******/ #define MAXQSIZE 10 /*最大队列长度*/ #define OK 1 #define ERROR -1 typedef int Status ; typedef int ElemType ; typedef struct { ElemType *base; /*初始化的动态分配存储空间*/ int front; /*头指针,若队列不为空,指向队列头元素*/ int rear; /*尾指针,若队列不为空,指向队列尾元素的下一个位置*/ }SqQueue; ②、构造空循环队列 /*构造一个空队列*/ Status InitQueue(SqQueue Q){ Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if(!Q.base) exit (0); /*存储分配失败退出*/ Q.front = Q.rear = 0; return OK; } ③、入队 /* 将数据元素e插入到循环队列Q的队尾 */ Status EnQueue(SqQueue Q, ElemType *e) { if ( ( Q.rear + 1 ) % MAXSIZE == Q.front ) /*判断队列是否满*/ return ERROR; /*队列满*/ Q.base[Q.rear] = e; /* 元素e入队 */ Q.rear = ( Q.rear + 1 ) % MAXSIZE; /* 队尾指针向前移动 */ return OK; /* 入队成功,返回OK */ } ④、出队 Status OutQueue(SqQueue Q, ElemType *e){ if (Q.rear == Q.front ) return ERROR; /*队列为空,返回错误*/ e = Q.base[Q.front]; /* 取队首元素 */ Q.front = ( Q.front + 1 ) % MAXSIZE;/* 队首指针向前移动 */ return OK; } ⑤、返回Q元素的个数,即队列的长度 /*返回Q元素的个数,即队列的长度*/ int QueueLength(SqQueue Q){ int i; i=(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; /*计算队中元素个数*/ return(i); } ⑥、遍历 void PrintQuence(SeQuence Q) { int i; i = (Q->Front + 1) % MAXQSIZE; /*队头加一开始遍历*/ while (i != Q->rear) { printf("%c", Q->base[i]); i = (i + 1) % MAXQSIZE; } printf("%c",Q->base[i]); /*队尾*/ printf("\n"); } 应用

1、桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩三张牌时进行以下操作：把第一、二张牌扔掉，然后把当前状态下新的第一张放到整叠牌的最后。输入n,输出每次扔掉的牌，以及最后剩下的牌。输入输出样例如下：输入4 第一次：扔掉1,2 从顶向底最后剩下：4,3

Queue.h #include #include #define OK 1 #define ERROR -1 #define MAX 100 typedef int QElemType; typedef struct { QElemType *data; int front;//队头 int rear;//队尾 }SqQueue; /*初始化*/ int InitiQueue(SqQueue &Q) { Q.data=(QElemType*)malloc(MAX*sizeof(QElemType)); if(!(Q.data)) { exit(0); } Q.front=Q.rear=0; return OK; } /*尾插法入队*/ int EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAX== Q.front) //队列满 { return ERROR; } Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MAX; return OK; } /*出队*/ int DeQueue(SqQueue &Q,QElemType &e){ if(Q.front == Q.rear) { return ERROR; } e=Q.data[Q.front]; Q.front=(Q.front+1)%MAX; return OK; } /*纸牌*/ int Playing_Cards(SqQueue &Q,QElemType &e) { int n,i=1; int number=1;//计数 printf("请输入的数量: "); scanf("%d",&n); printf("牌的编号为: "); for(i=1;i

【本文地址】

公司简介

联系我们