循环顺序队列

溯影

《数据结构C++描述》清华大学出版社    任燕编著

小弟还是老样子重载了输出运算符，并且写了一个main函数使程序可以运行，
加油！

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <cstdbool>
   
4. #include <assert.h>
   
5. using namespace std;
   
6. 
   
7. template <typename elemtype>
   
8. class SqQueue{
   
9. public:
   
10.         //循环队列置空
    
11.         void clear();
    
12. 
    
13.         //出队列
    
14.         bool deQueue(elemtype &e);
    
15. 
    
16.         //进队列
    
17.         bool enQueue(elemtype e);
    
18. 
    
19.         //读取循环队列队头元素
    
20.         bool getFront(elemtype &e);
    
21. 
    
22.         //求循环队列的元素的个数
    
23.         int getLength();
    
24. 
    
25.         //判断队列是否为空
    
26.         bool isEmpty();
    
27. 
    
28.         //判断队列是否已满
    
29.         bool isFull();
    
30. 
    
31.         //重载赋值运算符
    
32.         SqQueue operator=(SqQueue right);
    
33. 
    
34.         //构造函数
    
35.         SqQueue(int size = 10);
    
36. 
    
37.         //析构函数
    
38.         virtual ~SqQueue();
    
39. 
    
40.         //拷贝构造函数
    
41.         SqQueue(SqQueue &other);
    
42. 
    
43.         //重载输出运算符
    
44.         template <typename out_put>
    
45.         friend ostream& operator <<(ostream& out, SqQueue<out_put> other);
    
46. 
    
47. protected:
    
48.         int rear;//队尾指针
    
49.         int front;//对头指针
    
50.         int queueSize;//循环队列最大存储空间
    
51.         elemtype *base;//队列动态存储空间的首地址
    
52. };
    
53. 
    
54. 
    
55. template <typename elemtype>
    
56. void SqQueue<elemtype>::clear(){
    
57.         front = rear;
    
58. }
    
59. 
    
60. //出队列
    
61. template <typename elemtype>
    
62. bool SqQueue<elemtype>::deQueue(elemtype &e){
    
63.         if (isEmpty()){
    
64.                 return false;
    
65.         }
    
66.         e = base[front];
    
67.         front = (front + 1) % queueSize;//这里要取模，形成循环队列
    
68.         return true;
    
69. }
    
70. 
    
71. //进队列
    
72. template <typename elemtype>
    
73. bool SqQueue<elemtype>::enQueue(elemtype e){
    
74.         if (isFull()){
    
75.                 return false;
    
76.         }
    
77.         base[rear] = e;
    
78.         rear = (rear + 1) % queueSize;
    
79.         return true;
    
80. }
    
81. 
    
82. //读取队头元素
    
83. template <typename elemtype>
    
84. bool SqQueue<elemtype>::getFront(elemtype &e){
    
85.         if (isEmpty()){
    
86.                 return false;
    
87.         }
    
88.         e = base[front];
    
89.         return true;
    
90. }
    
91. 
    
92. //求队列中元素的个数
    
93. template <typename elemtype>
    
94. int SqQueue<elemtype>::getLength(){
    
95.         return (rear - front + queueSize) % queueSize;
    
96. }
    
97. 
    
98. //判断是否为空
    
99. template <typename elemtype>
    
100. bool SqQueue<elemtype>::isEmpty(){
     
101.         return front == rear ? true : false;
     
102. }
     
103. 
     
104. //判断队列是否已满
     
105. template <typename elemtype>
     
106. bool SqQueue<elemtype>::isFull(){
     
107.         return (rear + 1) % queueSize == front ? true : false;
     
108. }
     
109. 
     
110. //重载赋值运算符
     
111. template <typename elemtype>
     
112. SqQueue<elemtype> SqQueue<elemtype>::operator=(SqQueue<elemtype> right){
     
113.         if (this != &right){
     
114.                 if (queueSize != right.queueSize){
     
115.                         delete[] base;
     
116.                         base = new elemtype[right.queueSize];
     
117.                         assert(base != 0);
     
118.                         queueSize = right.queueSize;
     
119.                 }
     
120. 
     
121.                 front = right.front;
     
122.                 rear = right.rear;
     
123. 
     
124.                 for (int i = front; i%queueSize != rear;){
     
125.                         base[i] = right.base[i];
     
126.                         i = (i + 1) % queueSize;
     
127.                 }
     
128.         }
     
129.         return *this;
     
130. }
     
131. 
     
132. template <typename elemtype>
     
133. SqQueue<elemtype>::SqQueue(int size = 10){
     
134.         base = new elemtype[size];
     
135.         assert(base != 0);
     
136.         front = rear = 0;
     
137.         queueSize = size;
     
138. }
     
139. 
     
140. template <typename elemtype>
     
141. SqQueue<elemtype>:: ~SqQueue(){
     
142.         delete[]base;
     
143. }
     
144. 
     
145. //拷贝初始化构造函数
     
146. template <typename elemtype>
     
147. SqQueue<elemtype>::SqQueue(SqQueue &other){
     
148.         base = new elemtype[other.queueSize];
     
149.         assert(base != 0);
     
150.         queueSize = other.queueSize;
     
151. 
     
152.         front = other.front;
     
153.         rear = other.rear;
     
154. 
     
155.         for (int i = front; i%queueSize != rear;){
     
156.                 base[i] = other.base[i];
     
157.                 i = (i + 1) % queueSize;
     
158.         }
     
159. }
     
160. 
     
161. //重载输出运算符
     
162. template <typename out_put>
     
163. ostream& operator<<(ostream& out, SqQueue<out_put> other){
     
164.         for (int i = other.front; i%other.queueSize != other.rear;){
     
165.                 out << other.base[i] << "\t";
     
166.                 i = (i + 1) % other.queueSize;
     
167.         }
     
168.         return out;
     
169. }
     
170. 
     
171. 
     
172. int main(void){
     
173.         SqQueue<int> sq1;//默认传入的参数是10
     
174.         for (int i = 1; i <= 10; i++){
     
175.                 sq1.enQueue(i);
     
176.         }
     
177. 
     
178.         cout << "现在队列为:" << endl;
     
179.         cout << sq1 << endl;
     
180. 
     
181.         cout << "现在测试出队列函数:" << endl;
     
182.         cout << "只出前五个:" << endl;
     
183.         for (int i = 0; i < 5; i++){
     
184.                 int e;
     
185.                 sq1.deQueue(e);
     
186.                 cout << "出队列:" << e << endl;
     
187.         }
     
188.         cout << "现在队列为:" << endl;
     
189.         cout << sq1 << endl;
     
190.         return 0;
     
191. }
     

复制代码

运行结果:
现在队列为:
1       2       3       4       5       6       7       8       9
现在测试出队列函数:
只出前五个:
出队列:1
出队列:2
出队列:3
出队列:4
出队列:5
现在队列为:
6       7       8       9
请按任意键继续. . .