CODE
////////////////////////////////////////////////////////////////////////////////////
///////////////////// Queue.h //////////////////////////////
#ifndef QUEUE_H
#define QUEUE_H
namespace MyLibrary
{
#define MYLIBRARY_DEBUG
// MYLIBRARY_DEBUG 为测试而用
#ifdef MYLIBRARY_DEBUG
#include <iostream>
using std::ostream;
#endif
/// type def
#ifndef FALSE
#define FALSE false
#endif
#ifndef TRUE
#define TRUE true
#endif
typedef size_t size_type;
typedef bool BOOL;
/// 声明
template <typename _Ty> class Queue;
#ifdef MYLIBRARY_DEBUG
template <typename _Ty>
ostream & operator << ( ostream & , const Queue<_Ty> & );
#endif
//////////////////////// class ////////////////////////////
template <typename _Ty>
class Queue
{
//友元声明
#ifdef MYLIBRARY_DEBUG
friend ostream & operator << <> ( ostream &, const Queue<_Ty> & );
#endif
private:
//嵌套类定义
class QueueItem
{
public:
QueueItem( _Ty data ):_prior(0),_next(0),_data(data){}
public:
QueueItem * _prior; //前向指针
QueueItem * _next; //后向指针
_Ty _data; //数据
};
private:
//数据集
typename Queue<_Ty>::QueueItem * _head; //头结点指针
typename Queue<_Ty>::QueueItem * _tail; //尾结点指针
size_type _size; //长度
static const _Ty _temp; //只做空数据
public:
//构造析构集...
inline Queue():_head(0),_tail(0),_size(0){}
inline Queue( const Queue<_Ty> & );
inline ~Queue(){ while( !empty() )del(); }
public:
//外部操作接口集
inline const size_type size ( void ) const;
inline const BOOL empty ( void ) const;
inline const Queue & add ( const _Ty & );
inline const BOOL del ( void );
inline const BOOL del ( _Ty & );
inline const _Ty & get ( void )const;
public:
//重载操作符集
inline const Queue<_Ty> & operator = ( const Queue<_Ty> & );
inline const Queue<_Ty> & operator += ( const Queue<_Ty> & );
inline const Queue<_Ty> & operator += ( const _Ty & );
inline const Queue<_Ty> operator + ( const Queue<_Ty> & );
inline const Queue<_Ty> operator + ( const _Ty & );
inline const BOOL operator == ( const Queue<_Ty> & )const;
inline const BOOL operator != ( const Queue<_Ty> & )const;
};
template <typename _Ty>
inline const Queue<_Ty>
Queue<_Ty>::operator + ( const _Ty & value )
{
Queue<_Ty> temp = *this;
return temp+=value;
}
template <typename _Ty>
inline const Queue<_Ty> &
Queue<_Ty>::operator += ( const _Ty & value )
{
this->add( value );
return * this;
}
template <typename _Ty>
inline const Queue<_Ty>
Queue<_Ty>::operator + ( const Queue<_Ty> & queue )
{
// q=q1+q2;
if( queue.empty() )
{
return * this;
}
else
{
Queue<_Ty> temp = *this;
return temp += queue;
}
}
template <typename _Ty>
inline const Queue<_Ty> &
Queue<_Ty>::operator += ( const Queue<_Ty> & queue )
{
if( ! queue.empty() )
{
for( const typename Queue<_Ty>::QueueItem * it = queue._head;
it != queue._tail;
it = it->_prior )
{
this->add( it->_data );
}
this->add( queue._tail->_data );
}
return * this;
}
template <typename _Ty>
inline const BOOL
Queue<_Ty>::operator != ( const Queue<_Ty> & queue )const
{
if( queue.size() != this->size() )
{
return TRUE;
}
else
{
const typename Queue<_Ty>::QueueItem * youit = queue._tail;
const typename Queue<_Ty>::QueueItem * myit = this->_tail;
for(; myit != this->_head; myit=myit->_next,youit=youit->_next)
{
if( myit->_data != youit->_data )
{
return TRUE;
}
}
return (queue._head->_data != this->_head->_data)?TRUE:FALSE;
}
}
template <typename _Ty>
inline const BOOL
Queue<_Ty>::operator == ( const Queue<_Ty> & queue )const
{
if( queue.size() != this->size() )
{
return FALSE;
}
else
{
const typename Queue<_Ty>::QueueItem * youit = queue._tail;
const typename Queue<_Ty>::QueueItem * myit = this->_tail;
for(; myit != this->_head; myit=myit->_next,youit=youit->_next)
{
if( myit->_data != youit->_data )
{
return FALSE;
}
}
return (queue._head->_data != this->_head->_data)?FALSE:TRUE;
}
}
template <typename _Ty>
inline const Queue<_Ty> &
Queue<_Ty>::operator = ( const Queue<_Ty> & queue )
{
if( &queue == this )
{
return *this;
}
else
{
while( ! this->empty() )
{
this->del();
}
for( const typename Queue<_Ty>::QueueItem * it = queue._head;
it != queue._tail;
it = it->_prior )
{
this->add( it->_data );
}
this->add( queue._tail->_data );
return * this;
}
}
template <typename _Ty>
const _Ty Queue<_Ty>::_temp = _Ty();
template <typename _Ty>
inline const _Ty &
Queue<_Ty>::get( void )const
{
if( this->empty() )
return _temp; //返回表的空数据
else
{
return this->_head->_data;
}
}
template <typename _Ty>
inline const BOOL
Queue<_Ty>::del( void )
{
if( this->empty() )
return FALSE;
else
{
const typename Queue<_Ty>::QueueItem * temp = _head;
_head = _head->_prior;
--_size;
delete temp;
return TRUE;
}
}
template <typename _Ty>
inline const BOOL
Queue<_Ty>::del( _Ty & value )
{
if( this->empty() )
return FALSE;
else
{
const typename Queue<_Ty>::QueueItem * temp = _head;
value = temp->_data;
_head = _head->_prior;
--_size;
delete temp;
return TRUE;
}
}
template <typename _Ty>
inline const size_type
Queue<_Ty>::size(void)const
{
return _size;
}
template <typename _Ty>
inline const BOOL
Queue<_Ty>::empty( void )const
{
return (_size)?FALSE:TRUE;
}
template <typename _Ty>
inline const Queue<_Ty> &
Queue<_Ty>::add( const _Ty & value )
{
typename Queue<_Ty>::QueueItem * temp =
new typename Queue<_Ty>::QueueItem( value );
if( empty() )
{
_head = _tail = temp;
++_size;
}
else
{
temp->_next = _tail;
_tail->_prior = temp;
_tail = temp;
++_size;
}
return *this;
}
template <typename _Ty>
inline Queue<_Ty>::Queue( const Queue<_Ty> & queue )
:_head(0),_tail(0),_size(0)
{
if( this == &queue )
return;
for( const typename Queue<_Ty>::QueueItem * iter = queue._head;
iter != queue._tail;
iter = iter->_prior )
{
this->add( iter->_data );
}
this->add( queue._tail->_data );
return;
}
#ifdef MYLIBRARY_DEBUG
template <typename _Ty>
inline ostream & operator << ( ostream & os, const Queue<_Ty> & queue )
{
os<<"Queue("<<queue.size()<<"):\n";
os<<"head--->";
if( !queue.empty() )
{
for( const typename Queue<_Ty>::QueueItem * it = queue._head;
it != queue._tail;
it = it->_prior )
{
os<<it->_data<<" ";
}
os<<queue._tail->_data;
}
os<<"<---tail\n";
return os;
}
#endif
}////////// end namespace MyLibrary
#endif