竞赛：图解循环数组--借助循环数组进行队列的模拟实现以及循环数组的理解讲解

队列的模拟实现

队列是什么

队列是一种数据结构，遵循的是先进先出，后进后出的原则，基于这个原则我们可以借助数组进行模拟实现。

实现过程

实现原理

借助两个变量head和tail模拟实现队列的队头和队尾，出队列即让head++，入队即让tail++，即可借助数组实现模拟的队列过程

具体代码实现

#include <iostream>
using namespace std;
#define max 5

int queue[max] = { 0 };
int head = 0;
int tail = 0;

void Push(int num)
{
	if (tail >= max)
	{
		cout << "full!" << endl;
	}
	else
	{
		queue[tail] = num;
		tail++;
		cout << "successfully!" << endl;
	}
}

void Pop()
{
	if (head >= tail)
	{
		cout << "empty!" << endl;
	}
	else
	{
		head++;
		cout << "sucessfully!" << endl;
	}
}

void Display()
{
	for (int i = head; i < tail; i++)
	{
		cout << queue[i] << " ";
	}
	cout << endl;
}

int main()
{
	int num = 0;
	int opt = 1;
	while (opt)
	{
		cout << "1.push 2.pop 3.display 0.exit" << endl;
		cout << "your choice:->" << endl;
		cin >> opt;
		switch (opt)
		{
		case 1:
			cout << "your num:->";
			cin >> num;
			Push(num);
			break;
		case 2:
			Pop();
			break;
		case 3:
			Display();
			break;
		default:
			cout << "try again" << endl;
		}
	}
	return 0;
}

那么事实上，这样做确实可以达到目的，通过运行可以发现达到了最开始的想法，pop和push可以实现队列的整个过程

但与此同时，问题在于对于数组的利用有很大问题，出队后前面的部分就被荒废了，如果数组满了想要继续入队是不可行的，那么如何把这部分内容利用起来？于是我们就想到可以把前面的循环利用一下，这样就引出了循环数组的概念。

循环数组

循环数组是什么？

循环数组就是相当于把数组变成一个环形的数组，可以不断向里面存储内容

循环数组如何实现队列？

实现原理

我们要进行循环数组的原因就是前面的部分不能被充分利用，那么我们假设空出来一个格子不利用，专门用来进行循环。

图解如下：

由上图可以知道循环数组的原理就是少存储一个格子，而这个格子就是我们用来循环使用的，当tail指向最后一个格子而前面head没有出队的时候，此时就是队满了，而当head向前推进时，tail就可以循环到前面第一个格子，核心就是怎么进行这样的循环。
循环的原理就是head=(head+1)%maxn
maxn就是数组的大小。

//循环数组实现队列的模拟实现

#include <iostream>
using namespace std;
#define maxn 5

int queue[maxn];
int head = 0;
int tail = 0;

void Push(int num)
{
	queue[tail] = num;
	tail = (tail + 1) % maxn;
}

int Pop()
{
	int r = queue[head];
	head = (head + 1) % maxn;
	return r;
}

void Display()
{
	for (int i = head; i != tail; i = (i + 1) % maxn)
	{
		cout << queue[i] << " ";
	}
	cout << endl;
}

int main()
{
	int opt = 1;
	while (opt)
	{
		cout << "1.push 2.pop 3.display 0.exit" << endl << "your choice:->";
		cin >> opt;
		int num = 0;
		switch (opt)
		{
		case 1:
			if ((tail + 1) % maxn == head)
			{
				cout << "队列已满" << endl;
			}
			else
			{
				cin >> num;
				Push(num);
			}
			break;
		case 2:
			int r;
			if (head == tail)
			{
				cout << "队列为空" << endl;
			}
			else
			{
				r = Pop();
				if (r != -1)
					cout << r << " has pop" << endl;
			}
			break;
		case 3:
			Display();
			break;
		default:
			cout << "重新选择" << endl;
		}
	}
	return 0;
}

从这里看到和前面的比起来有一些区别，区别在于head和tail的增减情况发生了变化，原来只需要++现在变成了++后还要取模运算，而其实在取模运算的过程就是一个循环的过程。

总结

循环数组确实提供了一个全新思路，在很多题目中可以用循环数组解决一些看似很难的问题。
如有不对请多多指正。