數組是最最常用的數據結構之一，我們現在往數組中加入元素，當數組被加滿時，我們希望最早加入數組的元素就被沖掉，像一個隊列那樣，那應該如何實現呢？我寫了個類模板，非常簡單，初步測試下來還沒發現什么問題。
#pragma once
#define DEFAULT_ARRAY_SIZE 20
#define MINIMUM_ARRAY_SIZE 5
template <class T>
class CRollArray
{
public:
CRollArray(int iArraySize = DEFAULT_ARRAY_SIZE);
~CRollArray();
T& operator[] (int iIndex);
void Add(T element);
int GetSize();
void Reset();
private:
T* m_pData;
int m_iBegin;
int m_iEnd;
int m_iArrSize;
};
template <class T>
CRollArray<T>::CRollArray(int iArraySize)
{
if (iArraySize<MINIMUM_ARRAY_SIZE)
iArraySize=MINIMUM_ARRAY_SIZE;
m_pData = new T[iArraySize];
m_iBegin = -1;
m_iEnd = -1;
m_iArrSize = iArraySize;
}
template <class T>
CRollArray<T>::~CRollArray(void)
{
if(m_pData!=NULL)
delete[] m_pData;
}
template <class T>
T& CRollArray<T>::operator[] (int iIndex)
{
if (m_iBegin+iIndex<m_iArrSize)
return m_pData[m_iBegin+iIndex];
else
return m_pData[m_iBegin+iIndex-m_iArrSize];
}
template <class T>
void CRollArray<T>::Add(T element)
{
if(m_iEnd==m_iBegin-1)
{
// xxxxEB
if(m_iBegin==m_iArrSize-1)
{
m_iEnd = m_iBegin;
m_iBegin = 0;
}
// xxxEBx
else
{
++m_iEnd;
++m_iBegin;
}
}
else
{
// Null array.
if(m_iBegin==-1 && m_iEnd==-1)
{
m_iBegin = 0;
m_iEnd = 0;
}
else
{
// BxxxxE
if(m_iBegin==0 && m_iEnd==m_iArrSize-1)
{
++m_iBegin;
m_iEnd = 0;
}
// BxxExx
else
{
++m_iEnd;
}
}
}
m_pData[m_iEnd] = element;
}
template <class T>
int CRollArray<T>::GetSize()
{
if (m_iEnd==m_iBegin-1 || (m_iBegin==0 && m_iEnd==m_iArrSize-1))
return m_iArrSize;
if(m_iBegin==-1 && m_iEnd==-1)
return 0;
return m_iEnd-m_iBegin+1;
}
template <class T>
void CRollArray<T>::Reset()
{
m_iBegin = -1;
m_iEnd = -1;
}
這是測試代碼：
#include "RollArray.h"
int _tmain(int argc, _TCHAR* argv[])
{
CRollArray<int> arrTest(10);
printf("size: %d\n", arrTest.GetSize());
arrTest.Add(1);
printf("size: %d\n", arrTest.GetSize());
printf("idx0: %d\n", arrTest[0]);
arrTest.Reset();
printf("size: %d\n", arrTest.GetSize());
arrTest.Add(81);
arrTest.Add(4);
arrTest.Add(52);
arrTest.Add(123);
arrTest.Add(78);
arrTest.Add(987);
arrTest.Add(111);
printf("size: %d\n", arrTest.GetSize());
int i;
for(i=0; i<arrTest.GetSize(); i++)
printf("%d ", arrTest[i]);
printf("\n");
arrTest.Add(321);
arrTest.Add(3);
arrTest.Add(2);
arrTest.Add(7);
arrTest.Add(54);
arrTest.Add(276);
printf("size: %d\n", arrTest.GetSize());
for(i=0; i<arrTest.GetSize(); i++)
printf("%d ", arrTest[i]);
printf("\n");
arrTest.Add(94);
arrTest.Add(53);
arrTest.Add(40);
arrTest.Add(70);
arrTest.Add(102);
arrTest.Add(138);
arrTest.Add(461);
arrTest.Add(110);
printf("size: %d\n", arrTest.GetSize());
for(i=0; i<arrTest.GetSize(); i++)
printf("%d ", arrTest[i]);
printf("\n");
return 0;
}
代碼執行結果如下：
size: 0
size: 1
idx0: 1
size: 0
size: 7
81 4 52 123 78 987 111
size: 10
123 78 987 111 321 3 2 7 54 276
size: 10
54 276 94 53 40 70 102 138 461 110