【Weiss】【第03章】练习3.25：数组模拟队列

浏览数：22 / 时间：2015年06月08日

【练习3.25】

编写实现队列的例程，使用

a.链表

b.数组

Answer:

在这章一开头就已经写了个链表的队列例程了，所以实际上只要做b小题就可以。

数组模拟队列和链表的两点小不同是：

①、数组空间有限，入队需要检测数组是否已经满

②、数组经过几次操作后，rear可能绕回front前面，所以许多操作都要用模来实现。

测试代码：

 1 #include <iostream>
 2 #include "queue.h"
 3 using namespace std;
 4 using namespace queue;
 5 template class Queue<int>;
 6 int main(void)
 7 {
 8     Simu_Queue<int> test(6);
 9     //测试插入
10     test.enqueue(2);
11     test.enqueue(3);
12     test.enqueue(5);
13     test.enqueue(7);
14     test.enqueue(11);
15     test.enqueue(13);
16     test.enqueue(17);
17     test.traverse();
18     cout << endl;
19     //测试删除
20     test.dequeue();
21     test.dequeue();
22     test.dequeue();
23     test.traverse();
24     cout << endl;
25     //测试绕数组遍历
26     test.enqueue(17);
27     test.enqueue(19);
28     test.enqueue(23);
29     test.traverse();
30     cout << endl;
31 
32     system("pause");
33 }

View Code

实现代码：

 1 //练习3.25新增，用数组模拟队列
 2 template <typename T> class Simu_Queue
 3 {
 4 public:
 5     Simu_Queue() :head(nullptr), front(0), rear(0), size(0){}
 6     Simu_Queue(unsigned int _maxsize) :front(0), rear(0), maxsize(_maxsize){ head = new T[maxsize + 1]; }
 7     Simu_Queue(const Simu_Queue& another)
 8     {
 9         front = another.front;
10         rear = another.rear;
11         maxsize = another.maxsize;
12         head = new T[maxsize + 1];
13         for (unsigned i = 0; i < maxsize + 1; ++i)
14             head[i] = another.head[i];
15     }
16     ~Simu_Queue()
17     { 
18         delete[] head; 
19         front = rear = maxsize = 0;
20         head = nullptr;
21     }
22     Simu_Queue& operator=(const Simu_Queue& another)
23     {
24         if (this != &another)
25         {
26             delete[] head;
27             front = another.front;
28             rear = another.rear;
29             maxsize = another.maxsize;
30             head = new T[maxsize + 1];
31             for (unsigned i = 0; i < maxsize + 1; ++i)
32                 head[i] = another.head[i];
33         }
34     }
35 public:
36     //返回最大元素量
37     unsigned int size()const{ return maxsize; }
38     //返回当前元素量
39     unsigned int length()const{ return front <= rear ? rear - front : rear + maxsize + 1 - front; }
40     //判断是否为空
41     bool empty()const{ return front == rear; }
42     //入队
43     bool enqueue(const T &item)
44     {
45         if ((rear + 1) % (maxsize + 1) != front)
46         {
47             head[rear] = item;
48             rear = (rear + 1) % (maxsize + 1);
49             return true;
50         }
51         return false;
52     }
53     //出队
54     bool dequeue()
55     {
56         if (rear != front)
57         {
58             front = (front + 1) % (maxsize + 1);
59             return true;
60         }
61         return false;
62     }
63     //输出队列元素
64     void traverse()const
65     {
66         unsigned int temp = front;
67         while (temp != rear)
68         {
69             cout << " " << head[temp] << flush;
70             temp = (temp + 1) % (maxsize + 1);
71         }
72     }
73 private:
74     T* head = nullptr;
75     unsigned int front;
76     unsigned int rear;
77     unsigned int maxsize;
78 };