循环队列的数组（C/C++）实现及详细讲解_循环数组c++

本篇博客将实现循环队列的数组结构，实现功能有入队、出队、计算队列长度、判断队列是否为空、为满等。
队列的初始状态如下：

初始状态时，front=rear=0，size=0。

入队操作示意图如下：

入队时，在数组原来的rear位置插入数据，插入数据后将rear+1向后移动一位，同时将队列长度size+1。

如上图所示，当rear已经指向数组最后一个位置时，再进行入队操作，rear将重新回到起始位置0.

出队操作示意图如下所示：

当要将a元素出队时，原本指向a的front指针将移向下一个元素，同时将size-1。要注意的是这时的a其实还在数组中，只是不在有效区域，即实际存在于队列中的数据是front到rear之间的数组数据，而这时的a不在front到rear之间。

队列空满示意图如下：

如上图所示队列在空和满时，front和rear指针都将重合，因此将很难通过front和rear指针位置判断队列是空还是满。为了方便判断可以采取用实际队列的长度size来进行判断，即size=0时，队列为空；size=capacity（数组的最大容量）时，队列为满。

具体实现代码如下：
1.头文件CircleQueue.h

#pragma once
#ifndef CIRCLEQUEUE_H
#define CIRCLEQUEUE_H
#define NumOfQueue   10

typedef int ElementType;

struct queue
{
	int Capacity;
	int size;
	int front;
	int rear;
	ElementType* Array;
};

typedef struct queue* Queue;

Queue CreatQueue();//创建空队列；

int IsEmpty(Queue Q);//判断队列是否为空；

int IsFull(Queue Q);//判断队列是否为满；

void MakeEmpty(Queue Q);//置空

int LengthOfQueue(Queue Q);//计算队列长度

void EnQueue(Queue Q, ElementType data);//入队

void DeQueue(Queue Q);//出队

void PrintQueue(Q);//打印队列

#endif // !CIRCLEQUEUE_H

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
31
32
33
34
35
36

2.源文件CircleQueue.c

#include<stdio.h>
#include<malloc.h>
#include"CircleQueue.h"



Queue CreatQueue()//创建空队列；
{
	Queue Q = malloc(sizeof(struct queue));
	if (Q == NULL)
	{
		printf("out of space!!!");
		exit(1);
	}

	Q->Array = malloc(sizeof(ElementType) * NumOfQueue);
	if (!Q->Array)
	{
		printf("out of space!!!");
		exit(1);
	}

	Q->front = Q->rear = 0;
	Q->size = 0;
	Q->Capacity = NumOfQueue;


	return Q;
}



int IsEmpty(Queue Q)//判断队列是否为空；
{
	return Q->size ==0 ;
}



int IsFull(Queue Q)//判断队列是否为满；
{
	return Q->size == Q->Capacity;
}



void MakeEmpty(Queue Q)//置空
{
	Q->front = Q->rear = 0;
	Q->size = 0;
}



int LengthOfQueue(Queue Q)//计算队列长度
{
	return Q->size;
}



void EnQueue(Queue Q, ElementType data)//入队
{
	if (IsFull(Q))
	{
		printf("Enqueue Error:the queue is  full !!!");
		exit(1);
	}

	Q->Array[Q->rear++] = data;
	if (Q->rear == Q->Capacity)
		Q->rear = 0;

	++Q->size;
}



void DeQueue(Queue Q)//出队
{
	if (IsEmpty(Q))
	{
		printf("Dequeue Error: the queue is  empty !!!");
		exit(1);
	}

	++Q->front;
	if (Q->front == Q->Capacity)
		Q->front = 0;
	--Q->size;
}

void PrintQueue(Queue Q)//打印队列
{
	if (IsEmpty(Q))
	{
		printf("Print warning: the queue is  empty !!!");
		exit(1);
	}

	int i = Q->front;
	if(Q->rear>Q->front)
	for (; i < Q->rear; i++)
	{
		printf("%d ", Q->Array[i]);
	}

	else
	for (; i < Q->front+Q->size; i++)
	{
			printf("%d ", Q->Array[i%Q->Capacity]);
	}
	
	printf("\n");
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

3.主程序main.c

/********************************************************************************************************
Function：循环队列的数组实现
Date：2020/06/02
*********************************************************************************************************/

#include"CircleQueue.h"


int main()
{
	Queue Q=CreatQueue();//创建一个空队列

	for (int i = 0; i < 10; i++)
	{
		EnQueue(Q, i);//入队
	}
	PrintQueue(Q);//打印队列
	printf("the length of the queue is:%d\n", LengthOfQueue(Q));//打印队列长度


	for (int i = 0; i < 4; i++)
	{
		DeQueue(Q);//出队
	}
	PrintQueue(Q);//打印队列
	printf("the length of the queue is:%d\n", LengthOfQueue(Q));//打印队列长度


	for (int i = 0; i < 3; i++)
	{
		EnQueue(Q, i+10);//入队
	}
	PrintQueue(Q);//打印队列
	printf("the length of the queue is:%d\n", LengthOfQueue(Q));//打印队列长度
	

	MakeEmpty(Q);//置空
	PrintQueue(Q);//打印队列
	printf("the length of the queue is:%d\n", LengthOfQueue(Q));//打印队列长度


	return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43

4.运行结果