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;
   }