队列的模拟实现

队列是什么

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

实现过程

实现原理

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

具体代码实现

#include <iostream>
using namespace std;
#define max 5int 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 5int 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;
}