C++实现环形队列_c++ 环形队列

实现环形队列

线性队列原理图：

假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4， front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外 ，造成假溢出的现象：

为了解决这个问题，引入了循环队列的概念。

循环队列原理图：

可以看到当循环队列属于上图的d1情况时，是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的，可以通过牺牲一个存储空间来实现。如上图d2所示：

• 队头指针在队尾指针的下一位置时，队满。 Q.front == (Q.rear + 1) % MAXSIZE 因为队头指针可能又重新从0位置开始，而此时队尾指针是MAXSIZE - 1，所以需要求余。
• 当队头和队尾指针在同一位置时，队空。 Q.front == Q.rear。

还有一种方式是附加一个标志位tag ：

• 当head赶上tail，队列空，则令tag=0；
• 当tail赶上head，队列满，则令tag=1。

C++实现

const int maxn = 100;

template <class T>
class CircularQueue {
   
public:
    CircularQueue();
    CircularQueue(const int len);
    ~CircularQueue();

public:
    bool empty();
    bool full
1
2
3
4
5
6
7
8
9
10
11
12