带你一步步用C++实现循环队列_c++循环队列

前言

有关队列的介绍，如队列的常用操作，循环队列和链式队列的优缺点对比等，可参考队列简介及常用操作

创建一个Queue类，确定成员函数和数据成员

template <typename T>
class Queue
{
	Queue(int _capacity = 10);
	~Queue();

	void Push(const T& _data);//入队
	void Pop();//出队，既删除
	T& Front();//返回队首数据
	T& Rear();//返回队尾数据
	bool Empty();//判断队列是否为空
	int size();//返回队列的大小

private:
	T* queue;//顺序队列的存储数组
	int front;//队首标号
	int rear;//队尾标号
	int capacity;//队列的容量
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.什么时候循环队列为空

如果front 和rear都指向有数据的标号位置：

1. 在队列初始化时，front和rear都为0，此时队列是为空的,front = rear。
2. 当队列中只有一个数据时，front和rear都指向同一个位置，此时front=rear。
3. 当队列有两个以上数据时，front≠rear；

通过以上情况讨论，可以发现：如果front和rear都指向有数据的标号位置，当front=rear时，我们判断不了队列是空还是有一个数据。为此，我们可以空出一个元素，既让front指向队首的前一个元素（front空）或者让rear指向队尾的后一个元素（rear空），示意图如下。这样我们就可以用front=rear作为队列空的判断条件，仅仅影响的是队列的容量，比实际大小减1。

不难写出成员函数Empty()：

template <typename T>
bool Queue<T>::Empty()
{
	if (front == rear)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8

注意：后面的叙述，我都以“让front指向队首的前一个元素（front空）”为例来编写代码。

2.Push()操作

要处理两个问题：

• 何时队列满了?
• 当队列满了，怎样扩大队列？

(1)何时队列满了?

队列满的情况如下图所示：

当然，我们可以写出如下代码：

if (	(rear > front && (rear - front + 1) == capacity) ||
	(rear < front && rear + 1 == front)			)
{
	//队列满了
}
1
2
3
4
5

但是，我们有更简洁的方法，因为rear和front都是以队列大小(capacity)为一个环状进行改变，所以可以想到对capacity取余的方法。代码如下：

if ( (rear +1) % capacity == front )
{
	//队列满了
}
1
2
3
4

综上，我们就有了队列满的判断条件：(rear +1) % capacity == front

(2)当队列满了，怎样扩大队列？

方法很简单，申请新的内存，大小是原来的两倍。不过这里需要分情况讨论，分别针对的是队列满的两种情况。对于第一种情况，直接把从front到rear的数据复制到新的内存空间；对于第二种情况，需要分两段，第一段为front到队列下标capacity-1，另一段为队列下标0到rear。示意图如下：
第一种情况：

第二种情况：

现在可以写自动扩大队列的代码了：

		T * newQueue = new T[capacity * 2];//申请大的内存空间

		if (front < rear){
			//对应队列满的情况1
			std::copy(queue + front + 1, queue + rear + 1, newQueue);
		}
		else{
			//对应队列满的情况2
			T* rtnaddr = std::copy(queue + front + 1, queue + capacity, newQueue);
			std::copy(queue, queue + rear + 1, rtnaddr);
		}

		//重新确定rear和front的位置
		rear = capacity - 2;//不扩大之前的队列的元素个数为capacity-1
		capacity *= 2;//大小扩大一倍
		front = capacity - 1;//front指向数组的最后一个下标

		delete[] queue;//释放原来的内存
		queue = newQueue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意：由于C++编译器是不检查数组越界的，所以，即使程序员不自己扩容，使用越界的索引程序也不会报错，只是它会继续向下占用一块内存。程序员必须注意数组越界的问题。

扩容时使用了algorithm中的copy函数，有关std::copy()函数的介绍，可参考：C++ STL:algorithm 中的std::copy std::copy_backward函数

注意：使用std::copy时会报错，解决方法是：在预处理器加入(项目属性—>C/C++—>预处理—>预处理器定义)：_SCL_SECURE_NO_WARNINGS。

完整的push()代码如下：

template <typename T>
void Queue<T>::Push(const T& _data)
{
	//判断队列是否满了，满了就扩大队列
	if ( (rear +1) % capacity == front ){
		T * newQueue = new T[capacity * 2];//申请大的内存空间

		if (front < rear){
			//对应队列满的情况1
			std::copy(queue + front + 1, queue + rear + 1, newQueue);
		}
		else{
			//对应队列满的情况2
			T* rtnaddr = std::copy(queue + front + 1, queue + capacity, newQueue);
			std::copy(queue, queue + rear + 1, rtnaddr);
		}

		//重新确定rear和front的位置
		rear = capacity - 2;//不扩大之前的队列的元素个数为capacity-1
		capacity *= 2;//大小扩大一倍
		front = capacity - 1;//front指向数组的最后一个下标

		delete[] queue;//释放原来的内存
		queue = newQueue;
	}

	rear = (rear + 1) % capacity;
	queue[rear] = _data;
}
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

(3)std::copy()的用法

在扩大队列的过程中，我们使用了STL algorithm中的copy()函数，有关它的用法，我已近在C++ STL:algorithm 中的std::copy std::copy_backward函数中详细介绍了，感兴趣的小伙伴可以看看。

3.队列中现有多少个元素怎么算

不用想，肯定为front和rear的差值，但是需要考虑到回环的情况。若是rear>front，大小为rear-front；若是rear<front，肯定是rear回环了，所以先补回回环的大小，在减去front，即大小为rear + capacity – front。综合一下两种情况，用一个表达式表示：(rear + capacity – front)% capacity。举例，假设capacity = 6，若front = 1，rear = 4,此时大小为(4+6- 1)%6 = 3；若front = 4，rear = 1，此时大小为(1+6-4)%6 = 3。

所以，我们写出Size()的内容如下：

template <typename T>
int Queue<T>::Size()
{
	return (rear + capacity - front) % capacity;
}
1
2
3
4
5

4.其他成员函数

至于剩下的Pop()、Front()和Rear()，只需找到队首和队尾的位置即可。队尾的数据很简单，就是queue[rear]；front指向的位置由于是空的，所以队首的数据需要用回环操作，即queue[(front+1)%capacity]。

5.实例代码及运行结果：

Queue.h

#ifndef _QUEUE_H
#define _QUEUE_H

template <typename T>
class Queue
{
public:
	Queue(int _capacity = 10);
	~Queue();

	void Push(const T& _data);//入队
	void Pop();//出队，既删除
	T& Front();//返回队首数据
	T& Rear();//返回队尾数据
	bool Empty();//判断队列是否为空
	int Size();//返回队列的大小

private:
	T* queue;//顺序队列的存储数组
	int front;//队首标号
	int rear;//队尾标号
	int capacity;//队列的容量
};

//构造函数和析构函数
template <typename T>
Queue<T>::Queue(int _capacity)
:capacity(_capacity), queue(nullptr), front(0), rear(0)
{
	if (capacity < 1)
		exit(1);
	else
		queue = new T[capacity];
}
template <typename T>
Queue<T>::~Queue()
{
	delete[] queue;
}

//push
template <typename T>
void Queue<T>::Push(const T& _data)
{
	//判断队列是否满了，满了就扩大队列
	if ( (rear +1) % capacity == front ){
		T * newQueue = new T[capacity * 2];//申请大的内存空间

		if (front < rear){
			//对应队列满的情况1
			std::copy(queue + front + 1, queue + rear + 1, newQueue);
		}
		else{
			//对应队列满的情况2
			T* rtnaddr = std::copy(queue + front + 1, queue + capacity, newQueue);
			std::copy(queue, queue + rear + 1, rtnaddr);
		}

		//重新确定rear和front的位置
		rear = capacity - 2;//不扩大之前的队列的元素个数为capacity-1
		capacity *= 2;//大小扩大一倍
		front = capacity - 1;//front指向数组的最后一个下标

		delete[] queue;//释放原来的内存
		queue = newQueue;
	}

	rear = (rear + 1) % capacity;
	queue[rear] = _data;
}
template <typename T>
void Queue<T>::Pop()
{
	if (!Empty())
		front = (front + 1) % capacity;
	else
		exit(1);
}

template <typename T>
T& Queue<T>::Front()
{
	if (!Empty())
		return queue[(front + 1) % capacity];
	else
		exit(1);
}
template <typename T>
T& Queue<T>::Rear()
{
	if (!Empty())
		return queue[rear];
	else
		exit(1);
}

//判断队列是否为空
template <typename T>
bool Queue<T>::Empty()
{
	if (front == rear)
		return true;
	else
		return false;
}
//返回队列的大小
template <typename T>
int Queue<T>::Size()
{
	return (rear + capacity - front) % capacity;
}

#endif
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

main.cpp

#include <iostream>
#include "Queue.h"

using namespace std;

int main()
{
	cout << "测试队列的正确性:"<<endl;
	Queue<int> q(5);

	for (int i = 0; i < 5; i++){
		q.Push(i);
	}

	while (!q.Empty())
	{
		cout << "size = " << q.Size() << "\t";
		cout << "front = " << q.Front()<< endl;
		q.Pop();
	}

	cout << "\n测试队列的自动扩大功能:" << endl;
	for (int i = 0; i < 5; i++){
		q.Push(i);
	}
	q.Push(5);//队列大小为5，现在加入第6个数据

	while (!q.Empty())
	{
		cout << "size = " << q.Size() << "\t";
		cout << "front = " << q.Front() << endl;
		q.Pop();
	}

	system("pause");
	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

运行结果：

思考：

当我们把队列的初始大小定义为1时，push数据时发生了什么？
可以发现，此时必定满足队列满的条件：(rear +1) % capacity == front。所以我们是先把队列的大小扩大为2后，再把数据push进队列中。

总结

• 判空条件：front == rear
• 判满条件：(rear + 1) % capacity == front
• 队列中元素个数：(rear + capacity – front)%capacity
• 队首元素下标：(front + 1)%capacity
• 队尾元素下标：rear

到这里，我们就实现了C++版的循环队列，本人水平有限，欢迎各位码友批评指正。

相关文章：
（1）链式队列：数据结构——链式队列(C++)
（2）队列的介绍：队列简介及常用操作
（3）copy()的用法：C++ STL:algorithm 中的std::copy std::copy_backward函数