C++队列_c++ 队列

前言

队列的存储结构有链式和数组两种形式，链式队列较为简单，可以直接通过链表获得，而用数组实现队列则有很多细节，后文中会给出来，本文默认大家已经了解队列的先入先出的特点，重点在于代码实现，如果读者对队列还不熟悉建议先看看书或者视频再来看本文。

---

数组队列

类的定义

由于我们队列的两种形式都要实现，而两种队列的基本操作其实都是一样的，只不过是函数的实现不同，所以我们定义了抽象类

template<class Type>
 class queueADT
 {
 public:
	 virtual bool isEmpty()const = 0;
	 virtual bool isFull()const = 0;
	 virtual void initializeQueue() = 0;
	 virtual Type front()const = 0;
	 virtual Type back()const = 0;
	 virtual void addElem(const Type&) = 0;
	 virtual void deleteElem() = 0;
	 virtual int queueLen()const = 0;
 };
1
2
3
4
5
6
7
8
9
10
11
12
13

然后通过类的继承来构造数组队列类,我们将数组的最大容量作为成员变量方便初始化。

template<class Type>
class queueArr :public queueADT<Type>
{
public:
	const queueArr<Type>& operator=(const queueArr<Type>&);
	bool isEmpty()const;
	bool isFull()const;
	void initializeQueue();
	Type front()const;
	Type back()const;
	int queueLen()const;
	void addElem(const Type&);
	void deleteElem();
	queueArr(int size = 100);  //设置默认最大数组长度
	queueArr(const queueArr<Type>&);
	~queueArr();
	void printQueue()const;
private:
	int maxSize;
	int head;
	int tail;
	Type* headPtr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

成员函数的实现

• isEmpty:判断队列是否为空

template<class Type>
bool queueArr<Type>::isEmpty()const
{
	return tail == head;
}
1
2
3
4
5

注意:我们这里采用的区别队列满和空的手段是在数组中空一个位置，和王卓老师视频里用的方法一样，实际上比较简单的是将当前的元素数目作为成员变量,tail指针指向的是空置的位置。

• isFull:判断队列是否已满

template<class Type>
bool queueArr<Type>::isFull()const
{
	return (tail+1)%maxSize == head; 
}
1
2
3
4
5

• initializeQueue:初始化队列，这里的操作就是将头指针和尾指针都指向第一个元素

template<class Type>
void queueArr<Type>::initializeQueue()
{
	head = 0;
	tail = 0;
}
1
2
3
4
5
6

• front:获得队首元素

template<class Type>
Type queueArr<Type>::front()const
{
	assert(!isEmpty());  //防止队列为空返回错误值
	return headPtr[head];
}
1
2
3
4
5
6

• back:返回队尾元素

template<class Type>
Type queueArr<Type>::back()const
{
	assert(!isEmpty());
	return headPtr[(tail-1+maxSize)%maxSize]; 
	//注意tail如果为0那么减去1就会是负数，因此要加上数组容量，同时为了防止加了之后的
	//索引值超过了数组最大容量，所以要对maxSize取余
}
1
2
3
4
5
6
7
8

• queueLen:返回当前队列长度

template<class Type>
int queueArr<Type>::queueLen()const
{
	return (tail - head + maxSize) % maxSize;
}
1
2
3
4
5

注意:在数组队列中凡是涉及到指针的加减，通通要取余数，如果经过加减后可能出现负数，那么在取余前还要加上数组最大长度。循环计数的精髓就是要取余。

• addElem:向队列中添加元素(添加到队尾)

template<class Type>
void queueArr<Type>::addElem(const Type& elem)
{
	if (!isFull())
	{
		headPtr[tail] = elem;
		tail = (tail + 1) % maxSize;
	}
	else
		cout << "The queue is full,can not add an element in it" << endl;
}
1
2
3
4
5
6
7
8
9
10
11

• deleteElem:删除队首元素

template<class Type>
void queueArr<Type>::deleteElem()
{
	if (!isEmpty())
		head = (head + 1) % maxSize;
	else
		cout << "can not remove an element from the queue" << endl;
}
1
2
3
4
5
6
7
8

• 构造函数

template<class Type>
queueArr<Type>::queueArr(int size)
{
	if (size <= 0)
	{
		cout << "Size of the array to hold the queue must "
			<< "be positive." << endl;
		cout << "Creating an array of size 100." << endl;
		maxSize = 100;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr);
	}
	else
	{
		maxSize = size;
		head = 0;
		tail = 0;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr); //记得判断内存是否分配成功
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 拷贝构造

template<class Type>
queueArr<Type>::queueArr(const queueArr<Type>& otherQueue)
{
	head = otherQueue.head;
	tail = otherQueue.tail;
	maxSize = otherQueue.maxSize;
	headPtr = new Type[maxSize];
	assert(headPtr != nullptr);
	for (int i = 0; i < otherQueue.queueLen(); i++)
		headPtr[(head + i) % maxSize] = otherQueue.headPtr[(head + i) % maxSize];//特别注意，拷贝必须从队头开始拷贝(即从head处开始)，一直拷贝到队尾，拷贝长度就是队列的长度
}
1
2
3
4
5
6
7
8
9
10
11

• 析构函数

template<class Type>
queueArr<Type>::~queueArr()
{
	delete[]headPtr;
}
1
2
3
4
5

• =运算符重载

template<class Type>
const queueArr<Type>& queueArr<Type>::operator=(const queueArr<Type>& otherQueue)
{
	if (this != &otherQueue)
	{
		head = otherQueue.head;
		tail = otherQueue.tail;
		if (maxSize != otherQueue.maxSize)
		{
			delete[]headPtr;
			headPtr = new Type[otherQueue.maxSize];
			assert(headPtr != nullptr);
		}
		maxSize = otherQueue.maxSize;
		if (!otherQueue.isEmpty())
		{
			for (int i = 0; i < otherQueue.queueLen(); i++)
				headPtr[(head+i)%maxSize] = otherQueue.headPtr[(head + i) % maxSize];  //神来之笔，不然因为空了一个元素，而且元素位置不确定，一旦赋值就会出现问题
		}
	}
	else
	{
		cout << "cannot self assignment" << endl;
	}
	return *this;
}
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

• printQueue:打印队列的信息

template<class Type>
void queueArr<Type>::printQueue()const
{
	if (!isEmpty())
	{
		cout << "The queue:";
		for (int i = 0; i < queueLen(); i++)
		{
			cout << headPtr[(head + i) % maxSize] << " ";
		}
		cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

全部代码

链式队列很多操作和链表类似，也可以直接从链表获得，这里就不详细介绍了，不过还是给出代码以供参考。

queueADT.h

#pragma once
#include<iostream>
using namespace std;
 template<class Type>
 class queueADT
 {
 public:
	 virtual bool isEmpty()const = 0;
	 virtual bool isFull()const = 0;
	 virtual void initializeQueue() = 0;
	 virtual Type front()const = 0;
	 virtual Type back()const = 0;
	 virtual void addElem(const Type&) = 0;
	 virtual void deleteElem() = 0;
	 virtual int queueLen()const = 0;
 };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

queueArr.h

#pragma once
#include<iostream>
#include<assert.h>
#include "queueADT.h"
template<class Type>
class queueArr :public queueADT<Type>
{
public:
	const queueArr<Type>& operator=(const queueArr<Type>&);
	bool isEmpty()const;
	bool isFull()const;
	void initializeQueue();
	Type front()const;
	Type back()const;
	int queueLen()const;
	void addElem(const Type&);
	void deleteElem();
	queueArr(int size = 100);
	queueArr(const queueArr<Type>&);
	~queueArr();
	void printQueue()const;
private:
	int maxSize;
	int head;
	int tail;
	Type* headPtr;
};

template<class Type>
bool queueArr<Type>::isEmpty()const
{
	return tail == head;
}

template<class Type>
bool queueArr<Type>::isFull()const
{
	return (tail+1)%maxSize == head;
}

template<class Type>
void queueArr<Type>::initializeQueue()
{
	head = 0;
	tail = 0;
}

template<class Type>
Type queueArr<Type>::front()const
{
	assert(!isEmpty());
	return headPtr[head];
}

template<class Type>
Type queueArr<Type>::back()const
{
	assert(!isEmpty());
	return headPtr[(tail-1+maxSize)%maxSize];
}

template<class Type>
int queueArr<Type>::queueLen()const
{
	return (tail - head + maxSize) % maxSize;
}

template<class Type>
void queueArr<Type>::addElem(const Type& elem)
{
	if (!isFull())
	{
		headPtr[tail] = elem;
		tail = (tail + 1) % maxSize;
	}
	else
		cout << "The queue is full,can not add an element in it" << endl;
}

template<class Type>
void queueArr<Type>::deleteElem()
{
	if (!isEmpty())
		head = (head + 1) % maxSize;
	else
		cout << "can not remove an element from the queue" << endl;
}

template<class Type>
queueArr<Type>::queueArr(int size)
{
	if (size <= 0)
	{
		cout << "Size of the array to hold the queue must "
			<< "be positive." << endl;
		cout << "Creating an array of size 100." << endl;
		maxSize = 100;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr);
	}
	else
	{
		maxSize = size;
		head = 0;
		tail = 0;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr); //记得判断内存是否分配成功
	}
}

template<class Type>
queueArr<Type>::queueArr(const queueArr<Type>& otherQueue)
{
	head = otherQueue.head;
	tail = otherQueue.tail;
	maxSize = otherQueue.maxSize;
	headPtr = new Type[maxSize];
	assert(headPtr != nullptr);
	for (int i = 0; i < otherQueue.queueLen(); i++)
		headPtr[(head + i) % maxSize] = otherQueue.headPtr[(head + i) % maxSize];
}

template<class Type>
queueArr<Type>::~queueArr()
{
	delete[]headPtr;
}

template<class Type>
const queueArr<Type>& queueArr<Type>::operator=(const queueArr<Type>& otherQueue)
{
	if (this != &otherQueue)
	{
		head = otherQueue.head;
		tail = otherQueue.tail;
		if (maxSize != otherQueue.maxSize)
		{
			delete[]headPtr;
			headPtr = new Type[otherQueue.maxSize];
			assert(headPtr != nullptr);
		}
		maxSize = otherQueue.maxSize;
		if (!otherQueue.isEmpty())
		{
			for (int i = 0; i < otherQueue.queueLen(); i++)
				headPtr[(head+i)%maxSize] = otherQueue.headPtr[(head + i) % maxSize];  //神来之笔，不然因为空了一个元素，而且元素位置不确定，一旦赋值就会出现问题
		}
	}
	else
	{
		cout << "cannot self assignment" << endl;
	}
	return *this;
}

template<class Type>
void queueArr<Type>::printQueue()const
{
	if (!isEmpty())
	{
		cout << "The queue:";
		for (int i = 0; i < queueLen(); i++)
		{
			cout << headPtr[(head + i) % maxSize] << " ";
		}
		cout << endl;
	}
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

queueLink.h

#pragma once
#include<iostream>
#include<assert.h>
#include "queueADT.h"
using namespace std;
template<class Type>
struct node
{
	Type elem;
	node<Type>* next;
};

template<class Type>
class queueLink:public queueADT<Type>
{
public:
	 bool isEmpty()const ;
	 bool isFull()const ;
	 void initializeQueue() ;
	 Type front()const ;
	 Type back()const ;
	 void addElem(const Type&) ;
	 void deleteElem() ;
	 int queueLen()const ;
	 queueLink();
	 queueLink(const queueLink<Type>&);
	 ~queueLink();
	 const queueLink<Type>& operator=(const queueLink<Type>&);
private:
	node<Type>* head;
	node<Type>* tail;
	int length;
	void copyQueue(const queueLink<Type>&);
};

template<class Type>
bool queueLink<Type> ::isEmpty()const
{
	return head == nullptr;
}

template<class Type>
bool queueLink<Type> ::isFull()const
{
	return false;
}

template<class Type>
void queueLink<Type>::initializeQueue()
{
	node<Type>* temp = head;
	while (head)
	{
		head = head->next;
		delete temp;
		temp = head;
	}
	tail = nullptr;
	length = 0;
}
template<class Type>
Type queueLink<Type>::front()const
{
	assert(!isEmpty());
	return head->elem;
}
template<class Type>
Type queueLink<Type>::back()const
{
	assert(!isEmpty());
	return tail->elem;
}
template<class Type>
void queueLink<Type>::addElem(const Type& elem)
{
	node<Type>* newNode = new node<Type>;
	newNode->elem = elem;
	newNode->next = nullptr;
	if (head == nullptr)
	{
		tail = newNode;
		head = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = tail->next;
	}
	length++;
}
template<class Type>
void queueLink<Type>::deleteElem()
{
	if (!isEmpty())
	{
		node<Type>* temp = head;
		head = head->next;
		delete temp;
		length--;
	}
	else
		cout << "The queue is empty,cannot remove an element" << endl;
}
template<class Type>
int queueLink<Type>::queueLen()const
{
	return length;
}
template<class Type>
queueLink<Type>::queueLink()
{
	head = nullptr;
	tail = head;
	length = 0;
}
template<class Type>
queueLink<Type>::~queueLink()
{
	initializeQueue();
}
template<class Type>
void queueLink<Type>::copyQueue(const queueLink<Type>& otherQueue)
{
	node<Type>* temp,otherCurrent;
	otherCurrent = otherQueue.head;
	if (head)
		initializeQueue();
	if (otherQueue.head)
	{
		head = new node<Type>;
		tail = head;
		head->elem = otherCurrent->elem;
		head->next = otherCurrent->next;
		otherCurrent = otherCurrent->next;
		length++;
		while (otherCurrent)
		{
			temp = new node<Type>;
			temp->next = otherCurrent->next;
			temp->elem = otherCurrent->elem;
			tail->next = temp;
			tail = tail->next;
			otherCurrent = otherCurrent->next;
			length++;
		}
	}
}
template<class Type>
queueLink<Type>::queueLink(const queueLink<Type>& otherQueue)
{
	copyQueue(otherQueue);
}
template<class Type>
const queueLink<Type>& queueLink<Type>::operator=(const queueLink<Type>& otherQueue)
{
	if (this != &otherQueue)
	{
		copyQueue(otherQueue);
	}
	return *this;
}

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

test.cpp

#include<iostream>
#include "queueArr.h"
#include "queueLink.h"
using namespace std;

int main()
{
	queueArr<int> que1,que2(4);
	que1.addElem(11);
	que1.addElem(12);
	que1.addElem(13);
	que1.addElem(13);
	que1.addElem(13);
	que1.printQueue();
	cout << que1.queueLen() << endl;
	que1.deleteElem();
	que1.addElem(44);
	que1.deleteElem();
	que1.addElem(32);
	que2 = que1;
	que1.printQueue();
	que2.printQueue();
	queueArr<int> que3(que1);
	que3.printQueue();
	que1.printQueue();
	cout << que1.queueLen() << endl;
	que2 = que1;
	que2.printQueue();
	que2.deleteElem();
	que2.deleteElem();
	que2.deleteElem();
	cout << que1.front() << "," << que1.back() << endl;

	queueLink<int> queL1,queL2;
	queL1.addElem(13);
	queL1.addElem(76);
	
	cout << queL1.front()<<" " << queL1.back();
	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