C语言数据结构学习：循环队列

C语言 数据结构学习 汇总入口：

C语言数据结构学习：[汇总]

1. 循环队列

1. 队列的博客：C语言数据结构学习：队列

• 循环队列会预先定义最大队列空间，然后定义一个数组，通过队列头和队列尾指针分别指向开头和结尾，添加节点时队列尾自动后移。

  

• 但是直接使用的话，会出现虚假满状态问题，也就是当队列尾循环一圈后，重新指向了队列头，导致无法判别队列是否为空或满

• 可通过另设标志位或少用一个元素空间这两种方法解决，此处采用少用一个元素空间的方法。

  • 也就是当队列尾的下一个元素为队列头时，表示队列已满

2. 循环队列的特点

1. 会出现虚假满状态问题，也就是当队列尾循环一圈后，重新指向了队列头，导致无法判别队列是否为空或满。可通过另设标志位或少用一个元素空间这两种方法解决，此处采用少用一个元素空间的方法。
2. 基本操作：
   • 初始化队列
   • 出队
   • 入队

3. 代码示例

1. 定义新的类型：Node，用于创建队列
2. #define MAXSIZE 5

#define MAXSIZE 5
/* 节点 */
typedef struct Queue {
	int front;	//定义队头指针
	int rear;	//定义队尾指针
	int data[MAXSIZE];
}Queue;

1. 初始化队列

   /* 初始化队列 */
   Queue* InitQueue() {
   	Queue* Q = (Queue*)malloc(sizeof(Queue));
   	Q->front = 0;
   	Q->rear = 0;
   	return Q;
   }
   

2. 入队，出队

   /* 检查队列是否为满 */
   Queue* isFULL(Queue* Q) {
   	if ((Q->rear + 1) % MAXSIZE == Q->front) {
   		return 1;
   	}
   	else{
   		return 0;
   	}
   }
   /* 入队 */
   int enQueue(Queue* Q, int data) {
   	if (isFULL(Q)) {
   		return -1;
   	}
   	else {
   		Q->data[Q->rear] = data;	//存进去
   		Q->rear = (Q->rear + 1) % MAXSIZE;	//++，循环的哈~
   		return 1;
   	}
   
   }
   
   /* 检查队列是否为空 */
   Queue* isEmpty(Queue* Q) {
   	if (Q->front == Q->rear) {
   		return 1;
   	}
   	else {
   		return 0;
   	}
   }
   /* 出队 */
   int deQueue(Queue* Q) {
   	if (isEmpty(Q)) {
   		return -1;
   	}
   	else{
   		int data = Q->data[Q->front];	//取出来
   		Q->front = (Q->front + 1) % MAXSIZE;	//++，循环的哈~
   		return data;
   	}
   }
   

3. 打印队列

   /* 打印队列 */
   void PrintQueue(Queue* Q) {
   	//判断队列中有多少个元素
   	int len = (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
   	int temp = Q->front;
   	for (int i = 0; i < len; i++){
   		printf("%d ", Q->data[temp]);
   		temp = (temp + 1) % MAXSIZE;
   	}
   	printf("NULL\\r\\n");
   }
   

4. 测试

   int main(void)
   {
   	Queue* Q = InitQueue();
   	enQueue(Q, 1);
   	enQueue(Q, 2);
   	enQueue(Q, 3);
   	enQueue(Q, 4);
   	PrintQueue(Q);
   	deQueue(Q);
   	deQueue(Q);
   	PrintQueue(Q);
   	return 0;
   }