循环队列
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
![[置顶] ※数据结构※→☆线性表结构（queue）☆============循环队列 顺序存储结构（queue circular sequence）（十）](http://img.it610.com/image/product/598e8f92e2da4e6b83d8d76fe7df5187.jpg)
条件处理
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满；
② 另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。
③ 设队列中元素个数大小，和内存大小个数。判断比较二个值是否相等。.
②、
③判断代码
/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL
AL_QueueCircularSeq<T>::IsFull() const
{
return (m_dwMaxSize <= Size()) ? TRUE:FALSE;
// /*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity)
// when the team is full.*/
// if (TRUE == IsEmpty()) {
// return FALSE;
// }
//
// return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;
}
假溢出
系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"。
举例
设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。 设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于 m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中 仍 有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。
解决办法
一是将队列元素向前“平移”（占用0至rear-front-1）；
二是将队列看成首尾相连，即循环队列（0..m-1）。
在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，
① 另设一布尔变量以区别队列的空和满；
② 另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就 在此6%6=0=front（0）。
③ 设队列中元素个数大小，和内存大小个数。判断比较二个值是否相等。.
本文采用 循环队列 解决 假溢出
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
![[置顶] ※数据结构※→☆线性表结构（queue）☆============循环队列 顺序存储结构（queue circular sequence）（十）](http://img.it610.com/image/product/1f2a1659c6a34528ae2bd4373c469e7e.jpg)
顺序存储结构
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.
顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。
顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
优点：
随机存取表中元素。缺点：插入和删除操作需要移动元素。
本代码默认list可以容纳的item数目为100个，用户可以自行设置item数目。当list饱和时，会自动以2倍的长度进行递增。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
C++完整个代码示例（代码在VS2005下测试可运行）
![[置顶] ※数据结构※→☆线性表结构（queue）☆============循环队列 顺序存储结构（queue circular sequence）（十）](http://img.it610.com/image/product/f21bba39af1249319123fd3b0e19d8bf.jpg)
AL_QueueCircularSeq.h
/**
@(#)$Id: AL_QueueCircularSeq.h 37 2013-09-09 04:10:00Z xiaoting $
@brief To take advantage of vector space, to overcome the "false overflow" phenomenon is: the vector space imagined as an end to
end of the ring, saying such a vector is cyclic vector. Stored in a queue which is called circular queue (Circular Queue).
A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation,
and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert
operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.
This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted
element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear
form.
////////////////////////////////Sequential storage structure//////////////////////////////////////////
Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called
the linear order of the table storage structure.
Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical
location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency.
Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming
language (e.g., c / c) of the array to describe.
The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing
all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between
the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node
corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main
disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
Benefits:
Random Access table elements. Disadvantages: insert and delete operations need to move elements.
@Author $Author: xiaoting $
@Date $Date: 2013-09-09 12:10:00 +0800 (周一, 09 九月 2013) $
@Revision $Revision: 37 $
@URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h $
@Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h 37 2013-09-09 04:10:00Z xiaoting $
*/
#ifndef CXX_AL_QUEUECIRCULARSEQ_H
#define CXX_AL_QUEUECIRCULARSEQ_H
///////////////////////////////////////////////////////////////////////////
// AL_QueueCircularSeq
///////////////////////////////////////////////////////////////////////////
template<typename T>
class AL_QueueCircularSeq
{
public:
static const DWORD QUEUESEQ_DEFAULTSIZE = 100;
static const DWORD QUEUESEQ_MAXSIZE = 0xffffffff;
/**
* Construction
*
* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
AL_QueueCircularSeq(DWORD dwSize = QUEUESEQ_DEFAULTSIZE);
/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
~AL_QueueCircularSeq();
/**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note Returns true queue is empty
* @attention
*/
BOOL IsEmpty() const;
/**
* Front
*
* @param VOID
* @return T
* @note Returns a reference to the first element at the front of the queue.
* @attention
*/
T Front() const;
/**
* Back
*
* @param VOID
* @return T
* @note Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
T Back() const;
/**
* Pop
*
* @param VOID
* @return T
* @note Removes an element from the front of the queue.
* @attention
*/
T Pop();
/**
* Push
*
* @param VOID
* @return DWORD
* @note Adds an element to the back of the queue.
* @attention
*/
VOID Push(const T& tTemplate);
/**
* Size
*
* @param VOID
* @return DWORD
* @note Returns the number of elements in the queue
* @attention
*/
DWORD Size() const;
/**
* Clear
*
* @param VOID
* @return VOID
* @note clear all data
* @attention
*/
VOID Clear();
protected:
private:
/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
VOID GetBuffer();
/**
* IsFull
*
* @param VOID
* @return BOOL
* @note the buffer is full?
* @attention
*/
BOOL IsFull() const;
public:
protected:
private:
T* m_pElements;
DWORD m_dwMaxSize;
DWORD m_dwSize;
DWORD m_dwFront;
DWORD m_dwRear;
};
/**
* Construction
*
* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T>
AL_QueueCircularSeq<T>::AL_QueueCircularSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00),
m_dwFront(0x00),
m_dwRear(0x00)
{
if (0x00 == m_dwMaxSize) {
//for memory deal
m_dwMaxSize = 1;
}
GetBuffer();
}
/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T>
AL_QueueCircularSeq<T>::~AL_QueueCircularSeq()
{
if (NULL != m_pElements) {
delete[] m_pElements;
m_pElements = NULL;
}
}
/**
* IsEmpty
*
* @param VOID
* @return BOOL
* @note Returns true queue is empty
* @attention
*/
template<typename T> BOOL
AL_QueueCircularSeq<T>::IsEmpty() const
{
return (0x00 == m_dwSize) ? TRUE:FALSE;
}
/**
* Front
*
* @param VOID
* @return T
* @note Returns a reference to the first element at the front of the queue.
* @attention
*/
template<typename T> T
AL_QueueCircularSeq<T>::Front() const
{
T tTypeTemp;
memset(&tTypeTemp, 0x00, sizeof(T));
if (TRUE ==IsEmpty()) {
return tTypeTemp;
}
return m_pElements[m_dwFront];
}
/**
* Back
*
* @param VOID
* @return T
* @note Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
template<typename T> T
AL_QueueCircularSeq<T>::Back() const
{
T tTypeTemp;
memset(&tTypeTemp, 0x00, sizeof(T));
if (TRUE ==IsEmpty()) {
return tTypeTemp;
}
return m_pElements[m_dwRear];
}
/**
* Pop
*
* @param VOID
* @return T
* @note Removes an element from the front of the queue.
* @attention
*/
template<typename T> T
AL_QueueCircularSeq<T>::Pop()
{
T tTypeTemp;
memset(&tTypeTemp, 0x00, sizeof(T));
if (TRUE ==IsEmpty()) {
return tTypeTemp;
}
tTypeTemp = m_pElements[m_dwFront];
memset(&m_pElements[m_dwFront], 0x00, sizeof(T));
m_dwFront = (m_dwFront+1)%m_dwMaxSize;
m_dwSize--;
return tTypeTemp;
}
/**
* Push
*
* @param VOID
* @return DWORD
* @note Adds an element to the back of the queue.
* @attention
*/
template<typename T> VOID
AL_QueueCircularSeq<T>::Push(const T& tTemplate)
{
if (TRUE == IsFull()) {
// full, need to get more work buffer
GetBuffer();
}
if (0x00 == m_dwFront && TRUE == IsEmpty()) {
//the first time Push, not need to ++
m_dwRear = 0x00;
}
else {
m_dwRear = (m_dwRear+1)%m_dwMaxSize;
}
m_pElements[m_dwRear] = tTemplate;
m_dwSize++;
}
/**
* Size
*
* @param VOID
* @return DWORD
* @note Returns the number of elements in the queue
* @attention
*/
template<typename T> DWORD
AL_QueueCircularSeq<T>::Size() const
{
return m_dwSize;
}
/**
* Clear
*
* @param VOID
* @return VOID
* @note clear all data
* @attention
*/
template<typename T> VOID
AL_QueueCircularSeq<T>::Clear()
{
memset(m_pElements, 0x00, sizeof(T)*Size());
m_dwSize = 0x00;
m_dwFront = 0x00;
m_dwRear = 0x00;
}
/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T> VOID
AL_QueueCircularSeq<T>::GetBuffer()
{
if ( (FALSE == IsFull()) &&(NULL != m_pElements) ) {
//we do not need to get more buffer
return;
}
if (NULL == m_pElements) {
if(0 < m_dwMaxSize){
//get the new work buffer
m_pElements = new T[m_dwMaxSize];
memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);
}
return;
}
//we need to get more buffer, store the previous pointer
T* pLastTpye = NULL;
DWORD pLastSize = 0x00;
// it will become to double
pLastSize = m_dwMaxSize;
pLastTpye = m_pElements;
if (QUEUESEQ_MAXSIZE == m_dwMaxSize) {
//can not get more buffer, please check the application
return;
}
else if (QUEUESEQ_MAXSIZE/2 < m_dwMaxSize) {
m_dwMaxSize = QUEUESEQ_MAXSIZE;
}
else {
m_dwMaxSize *= 2;
}
if(0 < m_dwMaxSize){
//get the new work buffer
m_pElements = new T[m_dwMaxSize];
memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);
}
//need to copy the last to the current
memcpy(m_pElements, pLastTpye, sizeof(T)*pLastSize);
//m_dwFront move to the front
m_dwFront = 0x00;
//m_dwFront move to the rear
m_dwRear = Size() - 1;
//free the last work buffer
delete[] pLastTpye;
pLastTpye = NULL;
}
/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL
AL_QueueCircularSeq<T>::IsFull() const
{
return (m_dwMaxSize <= Size()) ? TRUE:FALSE;
// /*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity)
// when the team is full.*/
// if (TRUE == IsEmpty()) {
// return FALSE;
// }
//
// return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;
}
#endif // CXX_AL_QUEUECIRCULARSEQ_H
/* EOF */
测试代码
#ifdef TEST_AL_QUEUECIRCULARSEQ
AL_QueueCircularSeq<DWORD> cQueueCircularSeq(1);
BOOL bEmpty = cQueueCircularSeq.IsEmpty();
std::cout<<bEmpty<<std::endl;
DWORD dwSize = cQueueCircularSeq.Size();
std::cout<<dwSize<<std::endl;
DWORD dwFront = cQueueCircularSeq.Front();
std::cout<<dwFront<<std::endl;
DWORD dwBack = cQueueCircularSeq.Back();
std::cout<<dwBack<<std::endl;
DWORD dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
cQueueCircularSeq.Push(999);
bEmpty = cQueueCircularSeq.IsEmpty();
std::cout<<bEmpty<<std::endl;
dwSize = cQueueCircularSeq.Size();
std::cout<<dwSize<<std::endl;
dwFront = cQueueCircularSeq.Front();
std::cout<<dwFront<<std::endl;
dwBack = cQueueCircularSeq.Back();
std::cout<<dwBack<<std::endl;
dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
for (DWORD dwCnt=1; dwCnt<5; dwCnt++) {
cQueueCircularSeq.Push(dwCnt);
dwBack = cQueueCircularSeq.Back();
std::cout<<dwBack<<std::endl;
}
dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
for (DWORD dwCnt=5; dwCnt<16; dwCnt++) {
cQueueCircularSeq.Push(dwCnt);
dwBack = cQueueCircularSeq.Back();
std::cout<<dwBack<<std::endl;
}
dwSize = cQueueCircularSeq.Size();
std::cout<<dwSize<<std::endl;
dwFront = cQueueCircularSeq.Front();
std::cout<<dwFront<<std::endl;
while (0x00 != cQueueCircularSeq.Size()) {
dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
}
bEmpty = cQueueCircularSeq.IsEmpty();
std::cout<<bEmpty<<std::endl;
dwSize = cQueueCircularSeq.Size();
std::cout<<dwSize<<std::endl;
dwFront = cQueueCircularSeq.Front();
std::cout<<dwFront<<std::endl;
dwBack = cQueueCircularSeq.Back();
std::cout<<dwBack<<std::endl;
dwPop = cQueueCircularSeq.Pop();
std::cout<<dwPop<<std::endl;
#endif
[置顶] ※数据结构※→☆线性表结构（queue）☆============循环队列 顺序存储结构（queue circular sequence）（十）
