介绍

环形队列是队列的一种特殊情况，也是基于队列的实现，队列是动态的集合，而环形队列则是固定长度的，当队列满时，则从队首删除元素。其原理基本和队列一致，都是实现先进先出的策略。

实现

先定义数据，并且初始化：

static int* g_circularQueue = nullptr;
static int g_maxLength = 0;
static int g_length = 0;
static int g_head = 0;
static int g_tail = 0;void init(int initLength)
{g_circularQueue = new int [initLength];g_maxLength = initLength;g_length = 0;g_head = 0;g_tail = 0;
}

接着，先定义判断环形队列是否满，或者空：

bool isFull()
{return g_maxLength == g_length;
}bool empty()
{return 0 == g_length;
}

然后，就是入队：

void enqueue(int element)
{if (isFull()){dequeue();}g_circularQueue[g_tail] = element;++ g_length;g_tail = (g_tail + 1 ) % g_maxLength;
}

入队之前，先判断是否满，如果满了，就先出队删除一个元素，再入队，入队之后，增加环形队列当前的长度，并且增加尾标志的值。这里用到%模符号，是因为g_tail不能大于g_maxLength。

下面就是出队：

int dequeue()
{assert(0 != g_length);int element = g_circularQueue[g_head];g_head = (g_head + 1) % g_maxLength;-- g_length;return element;
}

出队的时候减去当前长度，并且增加头的值。和尾一样，最大不能超过g_maxLength，所以用模%。

最后，用来释放内存：

void finit()
{assert(nullptr != g_circularQueue);delete [] g_circularQueue;
}

测试比较简单，就是输出头和尾的值，以及环形队列的长度：

int _tmain(int argc, _TCHAR* argv[])
{init(4);enqueue(1);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(2);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(3);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(4);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(5);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;dequeue();cout << "dequeue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;dequeue();cout << "dequeue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(1);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(2);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;enqueue(3);cout << "enqueue head = " << g_head << ", tail = " << g_tail <<", length = " << g_length << endl;finit();return 0;
}

输出： circularQueue-result