@[TOC]

队列的模拟实现

队列是什么

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

实现过程

实现原理

借助两个变量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的增减情况发生了变化，原来只需要++现在变成了++后还要取模运算，而其实在取模运算的过程就是一个循环的过程。

总结

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