- On: 2025-10-22 13:35:38
- By: admin
3.5.2 队列的顺序表示和实现
队列的物理存储可以用顺序结构，也可用链式存储结构，相应地队列的存储方式也分为两种，即顺序队列和链式队列、
队列的顺序表示——————用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 // 最大队列的长度
typedef struct{
QElemType* base; // 初始化的动态分配存储空间
int front; // 头指针
int rear; // 尾指针
int length; // 用来记录队列所存储的元素个数
}SqQueue;
为什么需要使用循环队列？
因为会发生上溢的情况下，会导致空间利用率不高，所以使用循环队列使空间利用率提高。所以我可以都上面的队列结构中指针进行修改，对队列中两个指针进行下标循环，即可解决问题。
解决思路
将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始的端空着，又可以从头使用空着的空间。当front为maxqsize时，也一样。这两个操作主要体现在入队和出队的操作当中。
这里需要注意的是，就是两个指针的循环是利用mod运算来是实现。
还有就是如何来表示队空和队满的情况，自己使用的是另外设置一个变量来进行记录队列的长度
初始化队列
【算法思想】初始情况下，front=rear=0,也就是说头指针和尾指针指向同一位置
【算法描述】
Status InitQueue(&Q){
Q.base=new QElemType[MAXQSIZE]; // 分配空间
//Q.base=(QElemType)malloc(sizeof(QElemType));
if(!Q.base) // 判断是否分配成功
exit(OVERFLOW);
Q.rear=Q.base=0;
Q.length=0;
}
求队列的长度
【算法描述】
int QueueLength(Q){
return Q.length;
}
循环队列入队操作
【算法思想】入队操作是在队尾进行操作。
【算法步骤】
1、首先是需要判断队列是否已满，然后进行插入操作
2、front指针所指向的位置空间进行赋值，值为参数所传递进来的值。
3、将front指针进行移动一位，并且将length进行加一即可。
【算法描述】
Status EnQueue(&Q,e){
if(Q.Length==MAXQSIZE){
return ERROR;
}
Q.base[Q.front]=e;
Q.front=(Q.front+1)%MAXQSIZE;
Q.length++;
return OK;
}
循环队列出队操作
【算法思想】出队操作是在队头进行操作
【算法步骤】
1、首先是判断队列是否为空，然后进行下面的操作。
2、将rear指针所指向的位置元素进行删除
3、将rear指针进行移动一位，并且将length减一即可。
【算法描述】
Status DeQueue(&Q,&e){
if(Q.length==0){
return ERROR;
}
e=Q.base[Q.rear];
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.length++;
return OK;
}
取队头元素
【算法描述】
SElemType GetHead(SqQueue Q){
// 首先是判断队列是否为空
if(Q.length==0){
return ERROR;
}
return Q.base[Q.front];
}