C++用数组和链表分别实现Queue
昨天写了《C++用数组和链表分别实现Stack》，今天就是《C++用数组和链表分别实现Queue》，
队列就是先来的先被处理掉，后来的就等，直到成为先来的，实现起来感觉和栈差不多。
模板好用的，功能强大，有些东东还是写成模板的好，废话昨天都说了，今天是不想说的，
博客园的哥们说我的博客不符合推荐到首页的要求，只好加几句废话。
链表版
template
<
typename T,typename container
>
class queue
{
public :
bool empty() const
{
return len == 0 ;
}
void checkEmpty()
{
if (empty())
{
throw new exception( " 队列中没有数据 " );
}
}
T & back()
{
checkEmpty();
return cur -> val;
}
const T & back() const
{
return back();
}
void pop()
{
checkEmpty();
if (head -> next == cur)
{
delete head -> next;
head -> next = NULL;
} else
{
node * tmp = head -> next;
head -> next = tmp -> next;
delete tmp;
}
-- len;
}
T & front()
{
checkEmpty();
return head -> next -> val;
}
const T & front() const
{
return front();
}
void push( const T & val)
{
node * tmp = new node(val);
cur -> next = tmp;
cur = tmp;
++ len;
}
queue()
{
initialize();
}
explicit queue( const container & cont)
{
initialize();
vector < int > ::const_iterator iter = cont.begin();
while (iter != cont.end())
{
push( * iter ++ );
}
}
~ queue()
{
node * tmp;
while (tmp != NULL)
{
tmp = head;
head = head -> next;
delete tmp;
tmp = NULL;
}
delete cur;
}
int size()
{
return len;
}
protected :
typedef struct node1
{
node1 * next;
T val;
node1(T v):val(v),next(NULL){}
}node;
private :
int len;
node * head;
node * cur;
void initialize()
{
head = new node( - 1 );
cur = head;
len = 0 ;
}
};
class queue
{
public :
bool empty() const
{
return len == 0 ;
}
void checkEmpty()
{
if (empty())
{
throw new exception( " 队列中没有数据 " );
}
}
T & back()
{
checkEmpty();
return cur -> val;
}
const T & back() const
{
return back();
}
void pop()
{
checkEmpty();
if (head -> next == cur)
{
delete head -> next;
head -> next = NULL;
} else
{
node * tmp = head -> next;
head -> next = tmp -> next;
delete tmp;
}
-- len;
}
T & front()
{
checkEmpty();
return head -> next -> val;
}
const T & front() const
{
return front();
}
void push( const T & val)
{
node * tmp = new node(val);
cur -> next = tmp;
cur = tmp;
++ len;
}
queue()
{
initialize();
}
explicit queue( const container & cont)
{
initialize();
vector < int > ::const_iterator iter = cont.begin();
while (iter != cont.end())
{
push( * iter ++ );
}
}
~ queue()
{
node * tmp;
while (tmp != NULL)
{
tmp = head;
head = head -> next;
delete tmp;
tmp = NULL;
}
delete cur;
}
int size()
{
return len;
}
protected :
typedef struct node1
{
node1 * next;
T val;
node1(T v):val(v),next(NULL){}
}node;
private :
int len;
node * head;
node * cur;
void initialize()
{
head = new node( - 1 );
cur = head;
len = 0 ;
}
};
数组版
template < typename T,typename container >
class queue
{
public :
bool empty() const
{
return head == rail;
}
void checkEmpty()
{
if (empty())
{
throw new exception( " 队列中没有数据 " );
}
}
// 队尾元素
T & back()
{
checkEmpty();
return arr[rail - 1 ];
}
const T & back() const
{
return back();
}
// 出队
void pop()
{
checkEmpty();
arr[head ++ ] = 0 ;
}
// 队头元素
T & front()
{
checkEmpty();
return arr[head];
}
const T & front() const
{
return front();
}
// 入队
void push( const T & val)
{
if (rail >= capacity){
capacity = (rail - head) * 2 ;
T * tmp = new T[capacity];
int j = 0 ;
for ( int i = head;i < rail;i ++ )
{
tmp[j ++ ] = arr[i];
}
delete arr;
arr = tmp;
rail = rail - head;
head = 0 ;
}
arr[rail ++ ] = val;
}
queue()
{
initialize( 4 );
}
queue( int capacity)
{
initialize(capacity);
}
explicit queue( const container & cont)
{
initialize(cont.size());
vector < int > ::const_iterator iter = cont.begin();
while (iter != cont.end())
{
push( * iter ++ );
}
}
~ queue()
{
delete arr;
}
// 队列中元素个数
int size()
{
return rail - head;
}
protected :
typedef struct node1
{
node1 * next;
T val;
node1(T v):val(v),next(NULL){}
}node;
private :
int capacity;
int head; // 对头元素的位置
int rail; // 对尾元素的位置
int * arr;
void initialize( int cap)
{
capacity = cap;
arr = new int [capacity];
head = rail = 0 ;
}
};
作者：陈太汉