综合分析

关于数组模拟环形队列的问题，有两点疑问。

为什么用数组模拟？
为什么要有环形队列？

刚开始想用数组模拟队列，因为数组索引方便，使用简单。但是数组模拟队列有几点局限性。数组是一个定长的类型，即一经分配，无法修改长度。但是我们在使用队列的时候，可能需要很多个数据，那么对于队列的长度选取就存在着问题。因此，聪明的人们开始想着用环形队列进行代替，即环岛一样，可以重复利用多余的空间。

那么在使用数组进行环形队列模拟的时候有几点问题需要解决：

1、这个类中需要什么成员变量？

存储该队列的最大数量、front指针位置、rear指针位置、内部数组，在这里我们为了方便，将数组的真实长度为MAXSIZE - 1，即空出一个位置来计算队列满和队列空的条件。
具体如下图所示：
在这里插入图片描述

2、front 和 rear 位置确定？

对于起始索引为 0 ，如C语言、c++、JAVA、Python需要从0开始进行，这时候我们需要将
front 和 rear 初始位置都是 0 ，front 指向当前数组的首元素位置，rear 指向当前队列末尾元素的下一个元素。
即先赋值再进行计算，这点必须要注意。
对于起始索引为 1 的数组，我们可以将 front 和 rear 起始位置分别设为0和0，或者是1和1。不同的是我们需要对不同的处理方法有不同的逻辑操作，我们需要对0初始化这种操作先进行计算下一个位置该往哪里放，对1初始化这种操作先进性赋值再进行下一个位置的计算，这点在程序中也有体现。不同的只是先计算还是先进行赋值。 需要注意的是：起始索引是1的这种情况有一个比较关心的问题是下一跳的位置，需要添加一个判断条件，否则永远无法到达 MAXSIZE 的位置。

3、队列中真实大小如何计算？

两种情况：
1、如果rear 比 front 大，那么真实大小为 rear - front。
2、如果rear 比 front 小，那么真实大小是 maxSize - front + rear。
综合一下，可以写成一个表达式为：
（maxSize - front + rear）% maxSize

4、队列空和满的条件是什么呢？

空的条件：front == rear
满的条件：（rear + 1） % maxSize == front

5、下一跳的条件是什么？
rear =（rear + 1） % maxSize；
front=（front+ 1） % maxSize；
需要注意的是上面提及的那个问题，如果索引从1开始，则需要考虑一个问题是如果下一跳是 0，需要给它过滤掉。
需要注意的是：maxSize中我们约定了一个空余位置，目的是什么呢？
因为如果不约定一个空余位置，队列满和队列空的条件相同。那么有其他的解决办法吗？可以通过设置flag变量的方法来解决，但是其逻辑不清晰。遂取后者。

0索引开始的代码实现（C++）

#include <iostream>
using namespace std;
class CircleArray { 
private:
    int maxSize; //设置最大值，注意
    int front;   //头部指针初始化为0
    int rear;   //尾部指针初始化为0
    int *list;
public:
    //进行初始化
    CircleArray(int size) { 
        maxSize = size;
        front = 0;
        rear = 0;
        list = new int[size];
    }
    //判断是否为循环队列是否为空
    bool isEmpty() { 
        return front == rear;
    }
    //判断是否已经满
    bool isFull() { 
        return (rear + 1) % maxSize == front;
    }
    //添加元素 返回值返回的是添加的元素下一个元素的下标
    int add(int n) { 
        if (isFull())
        { 
            cout << "队列已经满了" << endl;
            return -1;
        }
        list[rear] = n;
        rear = (rear + 1) % maxSize;
        return rear;
    }
    //弹出元素 返回删除的元素的值
    int get() { 
        if (isEmpty())
        { 
            cout << "队列是空的，弹出失败" << endl;;
            return -1;
        }
        int temp = list[front];
        front = (front + 1) % maxSize;
        return temp;
    }
    //遍历队列
    void show() { 
        if (isEmpty())
        { 
            cout << "队列为空,无法进行遍历" << endl;;
            return;
        }
        for (int i = front; i < front + size(); i++) { 
            printf("arr[%d]:%d\n", i % maxSize, list[i % maxSize]);
        }
    }
    //返回队列的有效元素的大小
    int size() { 
        return (maxSize - front + rear) % maxSize;
    }
    //返回头部的元素
    int head() { 
        if (isEmpty())
        { 
            cout << "队列是空的,无法返回头部元素" << endl;;
            return -1;
        }
        return list[front];
    }
};
int main(int argc, char* argv[]) { 
    CircleArray* circle = new CircleArray(4);
    char c;
    bool loop = true;
    while (loop)
    { 
        cout << "s（show）：显示所有数据 \t" << "a（add）：添加元素\n"
            << "g（get）：弹出队列首元素\t" << "e（isEmpty）：判断队列是否为空\n"
            << "f（isFull）：判断队列是否为满\t" << "x（exit）：退出程序\n"
            << "h（head）：返回头元素" << endl;
        cin >> c;
        switch (c)
        { 
        case 's':
            try { 
                circle->show();
            }
            catch (string a) { 
                if (a == "队列为空")
                { 
                    cout << "队列为空，无法进行显示" << endl;
                }
            }
            break;
        case 'a':
            cout << "请输出需要插入的数据：" << endl;
            try { 
                int a;
                cin >> a;
                circle->add(a);
            }
            catch (string e) { 
                if (e == "队列已经满了")
                { 
                    cout << "队列已经满了，无法添加元素" << endl;
                }
            }
            break;
        case 'e':
            if (circle->isEmpty())
            { 
                cout << "队列为空" << endl;
            }
            else
            { 
                cout << "队列非空" << endl;
            }
            break;
        case 'f':
            if (circle->isFull()) { 
                cout << "队列是满的" << endl;
            }
            else
            { 
                cout << "队列是空的" << endl;
            }
            break;
        case 'h':
            printf("头元素是：%d\n", circle->head());
            break;
        case 'x':
            loop = false;
            break;
        case 'g':
            try { 
                circle->get();
            }
            catch (string e) { 
                if (e == "队列是空的") { 
                    cout << "队列是空的，无法弹出元素" << endl;
                }
            }
            break;
        default:
            break;
        }
    }
    return 0;
}

从1索引开始的代码实现(Matlab)

这里运用到了 Matlab 中的面向对象编程。需要注意的是，如果进行

classdef CircleArr
    properties
        m_front
        m_rear
        m_MAXSIZE
        m_arr
    end
    methods
        function this = CircleArr(front,rear, MAXSIZE)
            if nargin == 3
                this.m_front = front;
                this.m_rear = rear;
                this.m_MAXSIZE = MAXSIZE;
                this.m_arr = linspace(0, 0, MAXSIZE);
            end
        end
        function full = is_full(this)
            if (mod((this.m_rear + 1) , this.m_MAXSIZE) == this.m_front)
                full = true;
            else
                full = false;
            end
        end
        function newobj = add1(this, value)
            if this.is_full()
                newobj = this;
                return;
            else
                this.m_arr(this.m_rear) = value; 
                this.m_rear = mod((this.m_rear + 1) , this.m_MAXSIZE);
                if this.m_rear == 0
                    this.m_rear = this.m_MAXSIZE;
                end
            end
            newobj = this;
        end
        function m_display(this)
            display(this.m_MAXSIZE)
            display(this.m_arr);
        end
        function empty = is_empty(this)
            if this.m_front == this.m_rear
                empty = true; 
            else
                empty = false;
            end
        end
        function [newobj,getNum] = get(this)
            if is_empty(this)
                getNum = '无法获取，已经空了';
            else
                getNum = this.m_arr(this.m_front);
                this.m_front = mod((this.m_front + 1),this.m_MAXSIZE);
                if this.m_front == 0
                    this.m_front = this.m_MAXSIZE;
                end
            end
            newobj = this;
        end
    end
end