以下是本人用C++類模板實現的一種數據結構——循環隊列。希望對人們有所幫助,也希望人們提出寶貴的意見!
//循環隊列
#ifndef _QUEUE_H_INCLUDED
#define _QUEUE_H_INCLUDED
template<typename T>
class _queue
{
public:
_queue(size_t _capacity = 1):capacity(_capacity), length(0), pBase(new T[_capacity]),
pHead(pBase), pLast(pBase){}
~_queue(){delete []pBase;}
void ClearQueue()
{
pHead = pBase;
pLast = pBase;
length = 0;
}
bool IsEmpty()const {return !length;}
size_t GetLength()const {return length;}
T& GetHead()const {return *pHead;}
void Push(T &e);
T Pop();
void vist();
private:
void NewMenory();
void Insert(T &e);
size_t capacity;
size_t length;
T *pBase;
T *pHead;
T *pLast;
};
template<typename T>
void _queue<T>::NewMenory()
{
T *ptmpNew(new T[2*capacity]);
T *ptmpNewCopy(ptmpNew);
T *ptmpheadCopy(pHead);
T *ptmplimit(pBase + capacity -1);
for(int i = 0; i <capacity; ++i)
{
*ptmpNewCopy = *ptmpheadCopy;
if(ptmpheadCopy == ptmplimit)
{
ptmpheadCopy = pBase;
continue;
}
++ptmpNewCopy;
++ptmpheadCopy;
}
delete []pBase;
pBase = ptmpNew;
pHead = pBase;
pLast = pBase + capacity;
capacity *= 2;
}
template<typename T>
void _queue<T>::Insert(T &e)
{
if(pLast != (pBase + capacity))
{
*pLast = e;
++pLast;
}
else
{
*pBase = e;
pLast = pBase + 1;
}
}
template<typename T>
void _queue<T>::Push(T &e)
{
++length;
if(length > capacity)
NewMenory();
Insert(e);
}
template<typename T>
T _queue<T>::Pop()
{
if(length > 0)
{
--length;
if(pHead == pBase + capacity -1)
{
T tmp(*pHead);
pHead = pBase;
return tmp;
}
return *(pHead++);
}
return *pBase;
}
template<typename T>
void _queue<T>::vist()
{
T *ptmphead(pHead);
T * const ptmplimit(pBase + capacity);
for(int i = 0; i<length; ++i)
{
if(ptmphead == ptmplimit)
ptmphead = pBase;
std::cout<<" '"<<*ptmphead<<"' ";
++ptmphead;
}
}
#endif // _QUEUE_H_INCLUDED