队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
克服假溢出的方法有两种：
一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；本文不探讨
另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1。在结构上采用这种技巧来存储的队列称为循环队列。
这样的话，出现一个问题：上图(b)、(c)情况无法准确判断哪一种，
为了解决此问题，我们在队列中牺牲一个存储单元，即
当Q.rear和Q.front之间只空一个存储单元时认为队列是满的
循环队列的顺序存储实现
0.数据结构声明
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 6 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElementType;
//顺序循环队列结构,注意需要牺牲一个空间
typedef struct{
QElementType data[MAXSIZE];
int front; //队列头
int rear; //队列尾
}SqQueue;
初始化
//**初始化**
Status InitSqQueue(SqQueue *SqQueue){
SqQueue->front = SqQueue->rear = 0;
return OK;
}
SqQueue SqQueue;
Status iStatus;
iStatus = InitSqQueue(&SqQueue);
清空
//**清空**
Status ClearSqQueue(SqQueue *SqQueue){
//顺序存储不需要释放空间
SqQueue->front = SqQueue->rear = 0;
return OK;
}
判断是否为空
//**判断是否为空**
BOOL IsEmpty(SqQueue SqQueue){
if (SqQueue.front == SqQueue.rear) {
return TRUE;
}
return FALSE;
}
判断队满
//判断队满
BOOL IsEnough(SqQueue SqQueue){
if ((SqQueue.rear + 1)%MAXSIZE == SqQueue.front) {
return TRUE;
}
return FALSE;
}
队列长度
//**队列长度**
Status QueueLength(SqQueue SqQueue){
if (IsEmpty(SqQueue)){
return 0;
}
return ((SqQueue.rear + MAXSIZE) - SqQueue.front) % MAXSIZE;
}
获取队头
Status QueueFront(SqQueue SqQueue,QElementType *data){
if (IsEmpty(SqQueue)) {
return ERROR;
}
*data = SqQueue.data[SqQueue.front];
return OK;
}
出队
//**出队**
Status QueueAway(SqQueue *SqQueue,QElementType *data){
if (IsEmpty(*SqQueue)) {
//队空
printf("此队列为空！无法出队\n");
return ERROR;
}
*data = SqQueue->data[SqQueue->front];
SqQueue->front = (SqQueue->front + 1) % MAXSIZE;
return OK;
}
入队
//**入队**
Status QueueEnter(SqQueue *SqQueue,QElementType data){
if (SqQueue->rear == (MAXSIZE-1)) {
//队满
printf("此队列已满！无法入队\n");
return ERROR;
}
if (IsEnough(*SqQueue)) {
//队满
printf("此队列已满！无法入队\n");
return ERROR;
}
SqQueue->data[SqQueue->rear] = data;
SqQueue->rear = (SqQueue->rear + 1) % MAXSIZE;
return OK;
}
遍历
//从队首到队尾依次每个元素打印
Status QueueReverse(SqQueue SqQueue){
if (IsEmpty(SqQueue)){
printf("此队列为空！\n");
return ERROR;
}
int index = SqQueue.front;
printf("此队列长度为：%d\n",QueueLength(SqQueue));
while (index < SqQueue.rear) {
printf("%d ",SqQueue.data[index]);
index = (index + 1) % MAXSIZE;
}
printf("\n");
return OK;
}
代码示例：
SqQueue SqQueue;
Status iStatus;
iStatus = InitSqQueue(&SqQueue);
if (iStatus == OK) {
QueueReverse(SqQueue);
//入队
printf("入队1~10\n");
for (int i = 1; i < 10; i++) {
QueueEnter(&SqQueue, i);
}
QueueReverse(SqQueue);
printf("清空队列\n");
ClearSqQueue(&SqQueue);
QueueReverse(SqQueue);
//入队
printf("入队101~110\n");
for (int i = 101; i < 110; i++) {
QueueEnter(&SqQueue, i);
}
QueueReverse(SqQueue);
QElementType pushData;
QueueAway(&SqQueue, &pushData);
printf("当前出队的是：%d\n",pushData);
QueueReverse(SqQueue);
QueueAway(&SqQueue, &pushData);
printf("当前出队的是：%d\n",pushData);
QueueReverse(SqQueue);
QueueAway(&SqQueue, &pushData);
printf("当前出队的是：%d\n",pushData);
QueueReverse(SqQueue);
QueueAway(&SqQueue, &pushData);
printf("当前出队的是：%d\n",pushData);
QueueReverse(SqQueue);
}else{
printf("此队列初始化失败！\n");
}
网友评论