前言：
看到许多面经说，有时候面试官要你自己当场用模板写出自己的vector容器。于是，我也琢磨着怎么自己动手写一个，可是本人才刚刚学C++模板编程不久，会的不多。不过，我恰好在C++ Primer上看到作者实现了自己的Queue，如果Queue自己实现了，相信Vector也不难了吧？当然这个Queue没有标准库queue的全部功能，只是有它的一部分。我想把书上的Queue敲下来，让自己练练手。
首先我们来画一下Queue的结构，这样有利于我们理解Queue的构造，使编程思路更加清晰。
Queue类的定义:
//放到Queue.h文件中
//Queue的完整定义 //先申明Queue类，因为QueueItem类要用到
#ifndef _QUEUE_HEAD_
#define _QUEUE_HEAD_
template <class type> class Queue; template <class Type>
std::ostream& operator<< (std::ostream&, const Queue<Type>&); template <class Type>
class QueueItem{
//让Queue类成为友元函数，这样Queue里面就可以直接访问QueueItem的私有变量
friend class Queue<Type>;
//将重载后的 << 函数设置为QueueItem的友元函数，以便访问QueueItem的私有变量
friend std::ostream&
operator<< <Type> (std::ostream&, const Queue<Type>&);
//private 成员变量
//复制构造函数
QueueItem(const Type &t):item(t),next() {};
//真正保存数据的成员变量
Type item;
//指向下一个节点的指针
QueueItem *next;
}; //QueueItem类 //下面定义Queue类 template <class Type> class Queue {
friend std::ostream&
operator << <Type> (std::ostream&, const Queue<Type>&);
public:
//默认构造函数
Queue():head(),tail(){}
//根据迭代器范围进行构造的构造函数
template <class It>
Queue(It beg, It end):head(),tail(){copy_elems(beg,end);}
//复制构造函数
Queue(const Queue& Q):head(),tail(){copy_elem(Q);}
//析构函数
~Queue(){destory();}
//赋值函数
Queue& operator = (const Queue&);
//根据迭代器赋值的赋值函数
template <class Iter> void assign(Iter,Iter);
//返队首元素
Type& front();
//根据const重载front函数，以供const对象调用
const Type& front() const;
//向队尾添加元素
void push(const Type&);
//删除队首元素
void pop();
//判断队列是否为空，如果是空返回1，否则返回1
bool empty () const {return head == ;}
private:
//指向队首元素的指针
QueueItem<Type> *head;
//指向队尾元素的指针
QueueItem<Type> *tail;
//删除队列中所有元素的函数
void destory();
//复制队列元素的函数
void copy_elems(const Queue&);
//根据迭代器范围复制队列元素的函数，模板形式
template <class Iter> void copy_elems(Iter,Iter);
};
#include "Queue.cc" //实现
#endif
Queue类的实现:
//放到Queue.cc文件中
//实现 << 的重载的实现
template<class Type> std::ostream&
operator << (std::ostream &os,const Queue<Type>&q)
{
os << "<";
QueueItem<Type> *p = q.head; //指向链表的头节点
for(;p;p = p->next)
{
os << p->item << " ";
}
os << ">";
return os;
} //Queue的赋值函数
template <class Type> //模板标志
Queue<Type>& //返回类型
Queue<Type>::operator=//作用域
(const Queue&org) //参数列表
{ //函数体
if(this == &org) //防止自己赋值给自己
return *this;
destory(); //先释放掉自己原来占有的内存资源
copy_elems(org); //复制元素
} //成员函数模板
template<class Type> //第一个模板是类模板
template<class Iter> //第二个模板是成员函数模板
void
Queue<Type>::assign(Iter beg, Iter end)
{
destory();
copy_elems(beg,end);
} //front函数
template<class Type>
Type& Queue<Type>::front()
{
return head->item;
} //const对象调用的const front函数
template<class Type>
const Type& Queue<Type>::front() const
{
return head->item;
} //向队尾添加元素
template <class Type>
void Queue<Type>::push(const Type& val)
{
QueueItem<Type> *p = new QueueItem<Type>(val);
if(p)
{
if(empty())
{
head = tail = p;
}
else
{
tail->next = p;
tail = p;
}
} } //从队首删除元素
template<class Type>
void Queue<Type>::pop()
{
QueueItem<Type> *p = head;
head = head->next;
delete p;
} //清空队列
template<class Type>
void Queue<Type>::destory()
{
while(!empty())
{
pop();
}
} //根据队列复制元素
template<class Type>
void Queue<Type>::copy_elems(const Queue &org)
{
for(QueueItem<Type> *pt = org.head; pt; pt->next)
push(pt->item); //复制
} //根据迭代器范围
template<class Type>
template<class Iter>
void Queue<Type>::copy_elems(Iter beg,Iter end)
{
while(beg != end)
{
push(*beg);
++beg;
}
}
测试Queue功能：
#include <iostream>
#include <vector>
#include "Queue.h" using namespace std; int main()
{
Queue<int> qi;
int i = ;
//
//
short a[] = {,,,};
vector<int> vi(a,a + );
Queue<int> qi2(a,a+);
qi.push(i);
qi.push();
qi.push();
cout << qi << endl;
cout << qi2 << endl;
qi2.assign(vi.begin(),vi.end());
cout << qi2 << endl;
qi.pop();
cout << qi << endl;
//cout << qi.front() << endl;
//cout << "No Error!" << endl;
return ;
}