C++模板Queue
最后更新于：2022-04-01 19:55:04
《C++ primer》中的一个例子，感觉对模板编程很有帮助，便从头到尾实现了一遍。内部机制实际上是一个链表，但对外呈现队列的特性。代码如下：
~~~
#ifndef __MYQUEUE_H__
#define __MYQUEUE_H__
#include
// 这里必须提前声明
template
class Queue;
template
std::ostream& operator << (std::ostream &, const Queue &);
template
class QueueItem {
// 声明友元关系
friend class Queue;
friend std::ostream& operator << (std::ostream &, const Queue &);
QueueItem(const Type &t) : item(t), next(NULL)
{}
Type item;
QueueItem *next;
};
template
class Queue {
public:
// 声明友元关系
friend std::ostream& operator << (std::ostream &, const Queue &);
Queue() : head(NULL), tail(NULL)
{}
Queue(const Queue &q) : head(NULL), tail(NULL)
{
copy_elems(q);
}
Queue& operator= (const Queue &);
~Queue()
{
destroy();
}
Type& front()
{
if (head == NULL)
throw exception("Queue is empty.");
return head->item;
}
const Type& front() const
{
if (head == NULL)
throw exception("Queue is empty.");
return head->item;
}
void push(const Type&);
void pop();
bool empty() const
{
return head == NULL;
}
private:
QueueItem *head; // 指向Queue头节点
QueueItem *tail; // 指向Queue尾节点
void copy_elems(const Queue &);
void destroy();
};
template
Queue& Queue::operator= (const Queue &q)
{
if (&q == this)
return *this;
destroy();
copy_elems(q);
return *this;
}
// 从尾添加一个节点
template
void Queue::push(const Type &t)
{
QueueItem *tmp = new QueueItem(t);
if (empty())
{
head = tail = tmp;
}
else
{
tail->next = tmp;
tail = tmp;
}
}
// 从头删除一个节点
template
void Queue::pop()
{
if (head != NULL)
{
QueueItem *tmp = head;
head = tmp->next;
delete tmp;
}
}
template
void Queue::destroy()
{
while (!empty())
pop();
}
template
void Queue::copy_elems(const Queue &q)
{
QueueItem *tmp = q.head;
while (tmp != NULL)
{
push(tmp->item);
tmp = tmp->next;
}
}
template
std::ostream& operator << (std::ostream &os, const Queue &q)
{
QueueItem *tmp = q.head;
while (tmp != NULL)
{
os << tmp->item << ' ';
tmp = tmp->next;
}
return os;
}
// Queue的特化版本
template <>
class Queue {
public:
// 声明特化版本的 operator<< 为友元
friend std::ostream& operator <<
(std::ostream &os, const Queue &q);
void push(const char *);
void pop()
{
real_queue.pop();
}
bool empty() const
{
return real_queue.empty();
}
std::string& front()
{
return real_queue.front();
}
const std::string& front() const // 基于const的成员函数重载
{
return real_queue.front();
}
private:
Queue real_queue;
};
void Queue::push(const char *val)
{
real_queue.push(val);
}
template <>
std::ostream& operator << (std::ostream &os, const Queue &q)
{
os << q.real_queue;
return os;
}
#endif
~~~
参考：
《C++ primer》
';