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

【练习3.25】

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

a.链表

b.数组

Answer:

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

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

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

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

测试代码：

 #include <iostream>

 #include "queue.h"

 using namespace std;

 using namespace queue;

 template class Queue<int>;

 int main(void)

 {

     Simu_Queue<int> test();

     //测试插入

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.traverse();

     cout << endl;

     //测试删除

     test.dequeue();

     test.dequeue();

     test.dequeue();

     test.traverse();

     cout << endl;

     //测试绕数组遍历

     test.enqueue();

     test.enqueue();

     test.enqueue();

     test.traverse();

     cout << endl;

     system("pause");

 }

实现代码：

 //练习3.25新增，用数组模拟队列

 template <typename T> class Simu_Queue

 {

 public:

     Simu_Queue() :head(nullptr), front(), rear(), size(){}

     Simu_Queue(unsigned int _maxsize) :front(), rear(), maxsize(_maxsize){ head = new T[maxsize + ]; }

     Simu_Queue(const Simu_Queue& another)

     {

         front = another.front;

         rear = another.rear;

         maxsize = another.maxsize;

         head = new T[maxsize + ];

         for (unsigned i = ; i < maxsize + ; ++i)

             head[i] = another.head[i];

     }

     ~Simu_Queue()

     {

         delete[] head;

         front = rear = maxsize = ;

         head = nullptr;

     }

     Simu_Queue& operator=(const Simu_Queue& another)

     {

         if (this != &another)

         {

             delete[] head;

             front = another.front;

             rear = another.rear;

             maxsize = another.maxsize;

             head = new T[maxsize + ];

             for (unsigned i = ; i < maxsize + ; ++i)

                 head[i] = another.head[i];

         }

     }

 public:

     //返回最大元素量

     unsigned int size()const{ return maxsize; }

     //返回当前元素量

     unsigned int length()const{ return front <= rear ? rear - front : rear + maxsize +  - front; }

     //判断是否为空

     bool empty()const{ return front == rear; }

     //入队

     bool enqueue(const T &item)

     {

         if ((rear + ) % (maxsize + ) != front)

         {

             head[rear] = item;

             rear = (rear + ) % (maxsize + );

             return true;

         }

         return false;

     }

     //出队

     bool dequeue()

     {

         if (rear != front)

         {

             front = (front + ) % (maxsize + );

             return true;

         }

         return false;

     }

     //输出队列元素

     void traverse()const

     {

         unsigned int temp = front;

         while (temp != rear)

         {

             cout << " " << head[temp] << flush;

             temp = (temp + ) % (maxsize + );

         }

     }

 private:

     T* head = nullptr;

     unsigned int front;

     unsigned int rear;

     unsigned int maxsize;

 };

巴特西

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

最新文章

热门文章