Question

实现一个循环队列模板类，并在main()函数里面测试。

实现一个循环队列模板类，并在main()函数里面测试。
其成员函数包括：
1.构造函数
2.析构函数
3.出队函数
4.入队函数
5.赋值运算符重载函数
6.拷贝构造函数
6.输出队列所有元素的函数（重载<<）

Answer 1

#pragma once
#include <iostream>

//声明模板，以便在Node中将Queue、operator<<声明为Node的特殊类型的友元
template<class Type> class Queue;
template<class Type> std::ostream& operator<< (std::ostream&, const Queue<Type>&);

//节点类
template<class T>
class Node
{
friend class Queue<T>;
friend std::ostream& operator<< <T> (std::ostream&, const Queue<T>&);
private:
Node(); //声明无参构造函数，不定义这个成员函数，可以禁止任何方式以无参形式创建Node对象
Node(const T &elem): m_element(elem),m_pNext(0){}
private:
T m_element; //队列每个元素保存数据的成员变量
Node *m_pNext; //后缀指针，指向队当前元素后面的下一个元素
};

//接口类
template<class Type>
class Queue
{
//输出操作符重载友元声明
friend std::ostream& operator<< <Type> (std::ostream&, const Queue<Type>&);
public:
Queue(): prear(0){}
public:
template<class It> Queue(It beg, It end): prear(0)
{ copy_elems(beg, end); }
//复制控制(拷贝构造函数、赋值操作符、析构函数)
Queue(const Queue &q): prear(0)
{ copy_elems(q); }
Queue& operator== (const Queue&);
~Queue(){destroy();}

//user Interface
// unchecked operation: front on an empty Queue is undefined
Type& front(){return prear->m_pNext->m_element;}
const Type& front(){return prear->m_pNext->m_element;}

void push(const Type&);
void pop();
bool empty(){ //测试队列是否为空
return prear == 0;
}
private:
Node<Type> *prear; //对尾指针，这个元素的m_pNext又指向对头，形参循环队列
/utility function
void destroy();
void copy_elems(const Queue&);
private: //成员模板，迭代一个其他类型的序列创建队列
template<class Iter> void copy_elems(Iter, Iter);
};

//成员定义
/********************友元操作符<<重定义********************/
template<class Type>
std::ostream& operator<< (std::ostream &os, const Queue<Type> &q)
{
os << "< ";
Node<Type> *p;
for(p = q.prear->m_pNext; p; p = p->m_pNext)
os << p->m_element << " ";
os << ">";
return os;
}
/********************push定义********************/
template<class Type>
void Queue<Type>::push(const Type &elems)
{
Node<Type> *pt = new Node<Type>(elems);
if(empty()){
prear = pt;
pt->m_pNext = prear;
}
else{
pt.m_pNext = prear->m_pNext;
prear->m_pNext = pt;
prear = pt;
}
}
/********************pop定义********************/
template<class Type>
void Queue<Type>::pop()
{
if (!empty())
{
Node<Type> *op = prear->m_pNext;
prear->m_pNext = op->m_pNext;
if (op == prear)
prear = 0;
delete op;
}
}
/********************destroy定义********************/
template<class Type>
void Queue<Type>::destroy()
{
while(!empty())
pop();
}
/********************copy_elems重载版本之一定义********************/
template<class Type>
void Queue<Type>::copy_elems(const Queue &orig)
{
if (empty())
return ;
Node<Type> *pt=orig.prear->m_pNext;
do
{
push(pt->m_element);
pt = pt->m_pNext
} while ( pt != orig.prear->m_pNext );
}
/********************copy_elems重载版本之二定义********************/
template<class Type> template<class Iter>
void Queue<Type>::copy_elems(Iter beg, Iter end)
{
while(beg != end)
{
push(*beg);
++beg;
}
}