环形队列（索引从0开始（C语言、C++、Java）、索引从1开始（Matlab））

超、凢脫俗 2022-12-01 15:36 185阅读 0赞

### 环形队列 ###

*  综合分析
 *  0索引开始的代码实现（C++）
 *  从1索引开始的代码实现(Matlab)

# 综合分析 #

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

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

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

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

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

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

**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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dfd2VpeGlhb3Rhbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8edf842260774698a7b8df0844a04749.png