《数据结构、算法与应用C++语言描述》使用C++语言实现数组双端队列

《数据结构、算法与应用C++语言描述》使用C++语言实现数组双端队列

完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_16arrayDeque/

定义

队列的定义

队列（queue）是一个线性表，其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾（back或rear），删除元素的那一端称为队首（front）。

队列的抽象数据类型

链表队列代码

数组双端队列实现

_19deque.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			无序的双端队列的抽象类的头文件
*/
#pragma once
#ifndef _DEQUE_H_
#define _DEQUE_H_
template<class T>
class deque
{
public:
	virtual ~deque() {}
	virtual bool empty() const = 0;//返回true,当且仅当队列为空
	virtual int size() const = 0;//返回队列中元素个数
	virtual T& front() = 0;//返回头元素的引用
	virtual T& back() = 0;//返回尾元素的引用
	virtual void pop_front() = 0;//删除首元素
	virtual void pop_back() = 0;//删除尾元素
	virtual void push_front(const T& theElement) = 0;//把元素theELment加入队首
	virtual void push_back(const T& theElement) = 0;//把元素theELment加入队尾
};
#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

_20arrayDeque.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组存储的无序的双端队列类的头文件
*/
#pragma once
#ifndef _ARRAYDEQUE_H_
#define _ARRAYDEQUE_H_
#include
#include
#include "_1myExceptions.h"
#include "_19deque.h"
/*测试函数*/
void arrayDequeTest();
template<class T>
class arrayDeque : public deque<T>
{
public:
	/*成员函数*/
	/*构造函数*/
	arrayDeque(int initialCapacity = 10);
	/*析构函数*/
	~arrayDeque() {
		delete[]  deque;
	}
	bool empty() const { return theFront == theBack; };//返回true,当且仅当队列为空
	int size() const { return (dequeLength - theFront + theBack)%dequeLength; };//返回队列中元素个数
	int capacity() const {
		return dequeLength - 1;
	}
	void clear() { theFront = theBack = 0; }
	T& front();//返回头元素的引用
	T& back();//返回尾元素的引用
	void pop_front();//删除首元素
	void pop_back();//删除尾元素
	void push_front(const T& theElement);//把元素theELment加入队首
	void push_back(const T& theElement);//把元素theELment加入队尾
	/*调整队列容量大小*/
	void resizeDeque(int newLength);
	void meld(arrayDeque<T>& a, arrayDeque<T>& b);
	void split(arrayDeque<T>& a, arrayDeque<T>& b);

	/*重载操作符*/
	/*重载[]操作符*/
	T operator[](int i) { return deque[(theFront + i + 1) % dequeLength]; }

	/*友元函数*/
	friend istream& operator>> <T>(istream& in, arrayDeque<T>& m);
	//输出但是不pop()元素
	friend ostream& operator<< <T>(ostream& out, arrayDeque<T>& m);
private:
	int theFront;       // 第一个元素的前一个位置
	int theBack;        // 最后一个元素的位置
	int dequeLength;    // 队列的容量，实质上比队列容量(不包含queueFront指向的那一个位置)大1
	T* deque;
};

/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayDeque<T>& m)
{
	int numberOfElement = 0;
	cout << "Please enter the number of element:";
	while (!(in >> numberOfElement))
	{
		in.clear();//清空标志位
		while (in.get() != '\n')//删除无效的输入
			continue;
		cout << "Please enter the number of element:";
	}
	T cinElement;
	for (int i = 0; i < numberOfElement; i++)
	{
		cout << "Please enter the element " << i + 1 << ":";
		while (!(in >> cinElement))
		{
			in.clear();//清空标志位
			while (in.get() != '\n')//删除无效的输入
				continue;
			cout << "Please enter the element " << i + 1 << ":";
		}
		m.push_back(cinElement);
	}
	return in;
}
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, arrayDeque<T>& m)
{
	int size = m.size();
	for (int i = 0; i < size; i++)
		out << m.deque[(m.theFront + i + 1) % m.dequeLength] << "  ";
	out << endl;
	return out;
}

/*构造函数*/
template<class T>
arrayDeque<T>::arrayDeque(int initialCapacity)
{
	if (initialCapacity < 1)
	{
		ostringstream s("");
		s << "Initial capacity = " << initialCapacity << "Must be > 0";
		throw illegalParameterValue(s.str());
	}
	deque = new T[initialCapacity + 1];
	dequeLength = initialCapacity + 1;
	theFront = theBack = 0;
}
/*返回头元素的引用*/
template<class T>
T& arrayDeque<T>::front()
{
	if(theFront == theBack)
		throw queueEmpty();
	return deque[(theFront + 1) % dequeLength];
}
/*返回尾元素的引用*/
template<class T>
T& arrayDeque<T>::back()
{
	if (theFront == theBack)
		throw queueEmpty();
	return deque[theBack];
}
/*删除首元素*/
template<class T>
void arrayDeque<T>::pop_front()
{
	/*检查是否为空，为空就抛出异常*/
	if (theFront == theBack)
		throw queueEmpty();
	/*不为空就删除首元素*/
	theFront = (theFront + 1) % dequeLength;
	deque[theFront].~T();
}
/*删除尾元素*/
template<class T>
void arrayDeque<T>::pop_back()
{
	/*检查是否为空，为空就抛出异常*/
	if (theFront == theBack)
		throw queueEmpty();
	/*不为空就删除尾元素*/
	deque[theBack].~T();
	if (theBack == 0)
		theBack = dequeLength - 1;
	else
		theBack--;
}
/*把元素theELment加入队首*/
template<class T>
void arrayDeque<T>::push_front(const T& theElement)
{
	/*判断队列是否满了，如果满了，就调整容量为原来的两倍*/
	if ((theFront + 1) % dequeLength == theBack)
		resizeDeque(2 * (dequeLength-1));
	deque[theFront] = theElement;
	if (theFront == 0)
		theFront = dequeLength - 1;
	else
		theFront = theFront - 1;
}
/*把元素theELment加入队尾*/
template<class T>
void arrayDeque<T>::push_back(const T& theElement)
{
	/*判断队列是否满了，如果满了，就调整容量为原来的两倍*/
	if ((theBack + 1) % dequeLength == theFront)
		resizeDeque(2 * (dequeLength - 1));
	theBack = (theBack + 1) % dequeLength;
	deque[theBack] = theElement;
}

/*调整队列容量大小*/
template<class T>
void arrayDeque<T>::resizeDeque(int newLength)
{
	T* temp = new T[newLength + 1];
	int size = min((*this).size(), newLength);
	for (int i = 0; i < size; i++)
		temp[i] = deque[(theFront + i + 1) % dequeLength];
	dequeLength = newLength + 1;
	theFront = newLength;
	theBack = size - 1;
	delete[] deque;
	deque = temp;
}

/*
创建一个新的队列，该表包含了a和b中的所有元素，其中a和b的元素轮流出现，表中的首
元素为a中的第一个元素。在轮流排列元素时，如果某个队列的元素用完了，则把另一个队列的其
余元素依次添加在新队列的后部。代码的复杂性应与两个输入队列的长度呈线性比例关系。
归并后的线性队列是调用对象*this
*/
template <class T>
void arrayDeque<T>::meld(arrayDeque<T>& a, arrayDeque<T>& b)
{
	(*this).clear();
	int i = 0;
	while (i < a.size() && i < b.size())
	{
		push_back(a[i]);
		push_back(b[i]);
		i++;
	}
	while (i < a.size())
	{
		push_back(a[i]);
		i++;
	}
	while (i < b.size())
	{
		push_back(b[i]);
		i++;
	}
}

/*生成两个线性队列a和b，a包含*this中索引为奇数的元素，b包含其余的元素*/
template<class T>
void arrayDeque<T>::split(arrayDeque<T>& a, arrayDeque<T>& b)
{
	a.clear();
	b.clear();
	int size = (*this).size();
	for (int i = 0; i < size; i++)
	{
		if (i % 2 == 0)
			a.push_back(deque[(theFront + i + 1) % dequeLength]);
		else
			b.push_back(deque[(theFront + i + 1) % dequeLength]);
	}
}

#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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

_20arrayDeque.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_20arrayDeque.h头文件中的所有函数
*/
#include 
#include "_20arrayDeque.h"
using namespace std;
/*测试函数*/
void arrayDequeTest()
{
	cout << endl << "*********************************arrayDequeTest()函数开始*************************************" << endl;
	arrayDeque<int> a;
	//测试输入和输出
	cout << endl << "测试友元函数*******************************************" << endl;
	cout << "输入输出************************" << endl;
	cin >> a;
	cout << "arrayDeque a is:" << a;
	cout << endl << "测试成员函数*******************************************" << endl;
	cout << "empty()*************************" << endl;
	cout << "a.empty() = " << a.empty() << endl;
	cout << "size()**************************" << endl;
	cout << "a.size() = " << a.size() << endl;
	cout << "capacity()**********************" << endl;
	cout << "a.capacity() = " << a.capacity() << endl;
	cout << "push_front()********************" << endl;
	cout << "before push_front() arrayDeque a is:" << a;
	a.push_front(99);
	a.push_front(22);
	cout << "after push_front() arrayDeque a is:" << a;
	cout << "push_back()*********************" << endl;
	cout << "before push_back() arrayDeque a is:" << a;
	a.push_back(99);
	a.push_back(22);
	cout << "after push_back() arrayDeque a is:" << a;
	cout << "front()*************************" << endl;
	cout << "a.front() = " << a.front() << endl;
	cout << "back()**************************" << endl;
	cout << "a.back() = " << a.back() << endl;
	cout << "pop_front()*********************" << endl;
	cout << "before pop_front arrayDeque a is:" << a;
	a.pop_front();
	a.pop_front();
	cout << "after pop_front arrayDeque a is:" << a;
	cout << "pop_back()**********************" << endl;
	cout << "before pop_back arrayDeque a is:" << a;
	a.pop_back();
	a.pop_back();
	cout << "after pop_back arrayDeque a is:" << a;
	cout << "resizeDeque()*******************" << endl;
	cout << "before resizeDeque a.capacity() = " << a.capacity() << endl;
	a.resizeDeque(4);
	cout << "after resizeDeque a.capacity() = " << a.capacity() << endl;
	cout << "resizeDeque a is:" << a;
	cout << "a.front() = " << a.front() << endl;
	cout << "a.back() = " << a.back() << endl;
	a.push_back(88);
	cout << "after resizeDeque a.capacity() = " << a.capacity() << endl;
	cout << "meld()**************************" << endl;
	arrayDeque<int> b;
	cin >> b;
	cout << "arrayDeque a is:" << a;
	cout << "arrayDeque b is:" << b;
	arrayDeque<int> c;
	c.meld(a, b);
	cout << "arrayDeque c is:" << c;
	cout << "split()*************************" << endl;
	arrayDeque<int> d;
	arrayDeque<int> e;
	c.split(d, e);
	cout << "arrayDeque c is:" << c;
	cout << "arrayDeque d is:" << d;
	cout << "arrayDeque e is:" << e;
	cout << "*********************************arrayDequeTest()函数结束*************************************" << 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

_1main.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数，控制运行所有的测试函数
*/
#include 
#include "_20arrayDeque.h"

int main()
{
	arrayDequeTest();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

_1myExceptions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include 
#include

using namespace std;

// illegal parameter value
class illegalParameterValue 
{
   public:
      illegalParameterValue(string theMessage = "Illegal parameter value")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal input data
class illegalInputData 
{
   public:
      illegalInputData(string theMessage = "Illegal data input")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal index
class illegalIndex 
{
   public:
      illegalIndex(string theMessage = "Illegal index")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds 
{
   public:
      matrixIndexOutOfBounds
            (string theMessage = "Matrix index out of bounds")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix size mismatch
class matrixSizeMismatch 
{
   public:
      matrixSizeMismatch(string theMessage = 
                   "The size of the two matrics doesn't match")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// stack is empty
class stackEmpty
{
   public:
      stackEmpty(string theMessage = 
                   "Invalid operation on empty stack")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// queue is empty
class queueEmpty
{
   public:
      queueEmpty(string theMessage = 
                   "Invalid operation on empty queue")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// hash table is full
class hashTableFull
{
   public:
      hashTableFull(string theMessage = 
                   "The hash table is full")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
   public:
      undefinedEdgeWeight(string theMessage = 
                   "No edge weights defined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// method undefined
class undefinedMethod
{
   public:
      undefinedMethod(string theMessage = 
                   "This method is undefined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};
#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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131