C语言_数据结构总结7:顺序队列（循环队列）

纯C语言实现，不涉及C++

队列

简称队，也是一种操作受限的线性表。只允许表的一端进行插入，表的另一端进行删除
特性：先进先出

针对顺序队列存在的“假溢出”问题，引出的循环队列概念。

循环队列
将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环。
当队首指针Q->front=MaxSize-1 后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

循环队列中的判空和判满条件分析：
显然，队空的条件是Q.front == Q.rear。但若入队元素的速度快于出队元素，则队尾指针很快就会追赶上队首指针。
此时可以看出队满时也有：Q.front == Q.rear.
为此，有3中处理方法：
1. （推荐）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定“队头指针在队尾指针的下一个位置作为队满标志”
队满条件：(Q.rear + 1) % MaxSize == Q.front;
队空条件：Q.front == Q.rear;
队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize;

2. 在定义存储类型中，增设size数据成员，表示元素个数。
删除元素成功size减1；插入元素成功size加1.
队满时：Q.size == MaxSize;
队空时：Q.size == 0;
队空和队满时都有：Q.front == Q.rear;

3. 在定义存储类型中，增设tag数据成员,以区分是队满还是队空。
删除元素成功置tag=0,若导致Q.front == Q.rear;则为队空
插入元素成功置tag=1，若导致Q.front == Q.rear;则为队空

顺序队列（循环队列）的基本操作：

以下使用的方法是第一种处理方法，即牺牲一个单元来区分队空和队满。

0. 存储结构


#include<stdio.h>
#define MaxSize 50
typedef int ElemType;typedef struct SqQueue {ElemType data[MaxSize];  // 用数组存放队列元素int front;  // 队头指针.负责出队int rear;   //队尾指针，负责进队
}SqQueue;

1. 初始化

void InitQueue(SqQueue* Q) {Q->front = 0;Q->rear = 0;
}

2. 判空

int QueueEmpty(SqQueue* Q) {return Q->front == Q->rear;
}

3. 判满

int QueueFull(SqQueue* Q) {return (Q->rear + 1) % MaxSize == Q->front;
}

4. 入队

int EntreQueue(SqQueue* Q,ElemType value) {if (QueueFull(Q)){printf("队列已满，无法入队!\n");return -2;}Q->data[Q->rear] = value;Q->rear = (Q->rear + 1) % MaxSize;return 0;  //入队成功
}

5. 出队

int LeaveQueue(SqQueue* Q,ElemType* value) {if (QueueEmpty(Q)){printf("队列为空，无法有元素出队!\n");return -2;}*value = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return 0;  //出队成功
}

6. 打印

void printQueue(SqQueue* Q) {if (QueueEmpty(Q)){printf("队列为空，没有元素打印!\n");return;}int i = Q->front;printf("队列中的元素为：");while (i != Q->rear) {printf("%d ", Q->data[i]);i = (i + 1) % MaxSize;}printf("\n");
}

7. 注销

这里其实循环队列不需要特别的注销操作，只是为了保持接口统一

void destroyQueue(SqQueue* Q) {Q->front = 0;Q->rear = 0;
}

8. 测试

int main() {SqQueue Q;InitQueue(&Q);// 入队操作测试EntreQueue(&Q, 11);EntreQueue(&Q, 22);EntreQueue(&Q, 33);printQueue(&Q);  //队列中的元素为：11 22 33// 出队操作测试ElemType value;if (LeaveQueue(&Q,&value) == 0){printf("出队的元素是:%d\n", value);  // 出队的元素是:11}printQueue(&Q);  //队列中的元素为：22 33// 判空操作测试if (QueueEmpty(&Q)){printf("队列为空!\n");}else {printf("队列不为空!\n");  //队列不为空!}// 判满操作测试if (QueueFull(&Q)){printf("队列满了\n");}else {printf("队列还没满\n");  //队列还没满}// 注销队列destroyQueue(&Q);printQueue(&Q);  // 队列为空，没有元素打印!return 0;
}

9. 完整代码

#include<stdio.h>
#define MaxSize 50
typedef int ElemType;typedef struct SqQueue {ElemType data[MaxSize];  // 用数组存放队列元素int front;  // 队头指针.负责出队int rear;   //队尾指针，负责进队
}SqQueue;//操作1——初始化
void InitQueue(SqQueue* Q) {Q->front = 0;Q->rear = 0;
}//操作2——判空
int QueueEmpty(SqQueue* Q) {return Q->front == Q->rear;
}//操作3——判满
int QueueFull(SqQueue* Q) {return (Q->rear + 1) % MaxSize == Q->front;
}//操作4——入队
int EntreQueue(SqQueue* Q,ElemType value) {if (QueueFull(Q)){printf("队列已满，无法入队!\n");return -2;}Q->data[Q->rear] = value;Q->rear = (Q->rear + 1) % MaxSize;return 0;  //入队成功
}//操作5——出队
int LeaveQueue(SqQueue* Q,ElemType* value) {if (QueueEmpty(Q)){printf("队列为空，无法有元素出队!\n");return -2;}*value = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return 0;  //出队成功
}
//操作6——打印
void printQueue(SqQueue* Q) {if (QueueEmpty(Q)){printf("队列为空，没有元素打印!\n");return;}int i = Q->front;printf("队列中的元素为：");while (i != Q->rear) {printf("%d ", Q->data[i]);i = (i + 1) % MaxSize;}printf("\n");
}
//操作7——注销
// 这里其实循环队列不需要特别的注销操作，只是为了保持接口统一
void destroyQueue(SqQueue* Q) {Q->front = 0;Q->rear = 0;
}int main() {SqQueue Q;InitQueue(&Q);// 入队操作测试EntreQueue(&Q, 11);EntreQueue(&Q, 22);EntreQueue(&Q, 33);printQueue(&Q);  //队列中的元素为：11 22 33// 出队操作测试ElemType value;if (LeaveQueue(&Q,&value) == 0){printf("出队的元素是:%d\n", value);  // 出队的元素是:11}printQueue(&Q);  //队列中的元素为：22 33// 判空操作测试if (QueueEmpty(&Q)){printf("队列为空!\n");}else {printf("队列不为空!\n");  //队列不为空!}// 判满操作测试if (QueueFull(&Q)){printf("队列满了\n");}else {printf("队列还没满\n");  //队列还没满}// 注销队列destroyQueue(&Q);printQueue(&Q);  // 队列为空，没有元素打印!return 0;
}