使用数组实现循环队列 c语言_采用c语言使用数组来实现队列的存储,并在该物理结构上,实现循环队列的创建、判空

---

前言

最近学习时偶然发现了c语言使用数组实现循环队列的巧妙方法，将其记录下来以供之后参考

一、循环队列是什么？

首先要知道队列是什么，根据百度百科上的解释：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作.

简而言之，队列是一种只允许元素从后端进入，从前端弹出的数据结构，就如同在排队一般，先开始排队的人可以先排完队离开。
循环队列则是指使用数组来做底层实现，并且将数组抽象为了一个首尾相接的圆环，这样做的好处自然是可以充分利用数组空间，但同时也带来了队列的最大容量必定有限的缺点

二、c语言实现

1.整体结构

代码如下：

#define QUEUE_SIZE (1024)
struct queue {
	int data[QUEUE_SIZE];
	int front;
	int tail;
	int empty;
};

void init(struct queue *);
void enqueue(struct queue *, int);
int dequeue(struct queue *);
1
2
3
4
5
6
7
8
9
10
11

代码中采用了int作为队列要存储的数据类型，其中init用于初始化，enqueue用于入队，dequeue用于出队，成员变量中front用于记录的是队首索引，tail则记录的是队尾元素索引+1（可供插入的位置的索引）。
empty最为精妙，它用于判断队列是否为空，要知道循环队列实现的一大难处就是，初始时必然有tail == front，而当队满时，也有tail == front成立，那么该如何区分这两种场景呢？empty的作用便体现出来了，如若tail == front，则看empty的值，为0则队列满，为1则队列空，那么这一属性该如何维护呢，让我们来看具体代码。

2.函数实现

代码如下：

#include "queue.h"
#include <stdio.h>
void init(struct queue *q)
{
	q->front = q->tail = 0;
	q->empty = 1;
}

void enqueue(struct queue *q, int value)
{
	if (!q->empty && q->front == q->tail) {
		printf("queue shouldn't be overflow\n");
		exit(-1);
	}
	q->empty = 0;
	q->data[q->tail] = value;
	q->tail = (q->tail + 1) % QUEUE_SIZE;
}

int dequeue(struct queue *q)
{
	if (q->empty)
		return -1;
	int value = q->data[q->front];
	q->front = (q->front + 1) % QUEUE_SIZE;
	if (q->front == q->tail)
		q->empty = 1;
	return value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

可以看到，enqueue中就是向tail索引处插入元素并向后移动一位，而dequeue则是返回front索引处元素同时也向后移动一位；
两者都会操作empty，显然在enqueue中，由于有元素入队，调用之后队列必定不为空，empty必定为0，而dequeue时，由于会弹出元素，队列元素会减少，此时当q->front == q->tail时，必定说明队列为空，empty=1

---

总结

以上就是循环队列c语言的简单实现，上述思想也可适用于像c++、java等，都可通过数组来快速实现一循环队列