【C++】模板实现双链表和队列

首先来了解模板的定义

模板是泛型编程的基础，泛型编程是指编写与类型无关的逻辑代码，是一种复用方式。

模板分为模板函数和模板类

函数模板的格式：

template<class 形参名1，class 形参名2.......class 形参名n>

返回类型    函数名（参数列表）

{......}

类模板的格式：

template<class 形参名1，class 形参名2.......class 形参名n>

class  类名

{......}：

template<typename T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;

ListNode(const T& d)
:_next(NULL)
,_prev(NULL)
,_data(d)
{}
};

实现模板类

template<typename T>
class List
{
typedef ListNode<T> Node;
public:
List()
:_head(NULL)
, _tail(NULL)
{}

~List()
{
    Node* cur = _head;
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_head = _tail = NULL;
}

List(const List<T>& s)
:_head(NULL)
, _tail(NULL)
{
Node* cur = s._head;
while (cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}

List<T>& operator=(List<T> s)
{
swap(s._head, _head);
swap(s._tail, _tail);

return *this;
}

void PushBack(const T& d)
{
if (_head == NULL)
{
_head = _tail = new Node(d);
}
else
{
Node* newnode = new Node(d);
_tail->_next = newnode;
newnode->_prev = _tail;
_tail = newnode;
}
}

void PopBack()
{
if (_head==NULL)
{
return;
}
else if (_head == _tail)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* cur = _tail->_prev;
delete _tail;
_tail = cur;
_tail->_next = NULL;
}
}

void PushFront(const T& d)
{
if (_head == NULL)
{
_head = _tail = new Node(d);
}
else
{
Node* newnode = new Node(d);
newnode->_next = _head;
_head->_prev = newnode;
_head = newnode;
}
}

void PopFront()
{
if (_head == NULL)
{
return;
}
else if (_head == _tail)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* cur = _head->_next;
delete _head;
_head = cur;
_head->_prev = NULL;
}
}

Node* Find(const T& d)
{
Node* cur = _head;
while (cur)
{
if (cur->_data == d)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}

void Insert(const T& d, Node* pos)
{
assert(pos);

if (pos == _head)
{
PushFront(d);
}
else
{
Node* newnode = new Node(d);
Node* prev = pos->_prev;
newnode->_next = pos;
pos->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
}
}

void Erase(Node* pos)
{
assert(pos);

if (pos == _head)
{
PopFront();
}
else if (pos == _tail)
{
PopBack();
}
else
{
Node* del = pos;
Node* prev = pos->_prev;
Node* next = pos->_next;
prev->_next = next;
next->_prev = prev;
delete del;
del = NULL;
}
}

void Print()
{
Node* cur = _head;
while (cur)
{
cout << cur->_data << " ";
cur = cur->_next;
}
cout << endl;
}
protected:
    Node* _head;
    Node* _tail;
};

用适配器实现队列

template<class T,class Container>
class Queue
{
public:
    void Push(const T& d)
    {
        _con.PushBack(d);
    }

    void Pop()
    {
        _con.PopFront();
    }

    T& Front()
    {
        return _con.Front();
    }

    T& Back()
    {
        return _con.Back();
    }

    size_t Size()
    {
        return _con.Size();
    }

    bool Empty()
    {
        return _con.Empty();
    }

protected:
    Container _con;
};

在模板类中实现队列中的接口函数

        T& Front()
{
assert(_head);
return _head->_data;
}

T& Back()
{
assert(_tail);
return _tail->_data;
}

size_t Size()
{
size_t count = 0;
Node* cur = _head;
while (cur)
{
count++;
cur = cur->_next;
}
return count;
}

bool Empty()
{
return _head == NULL;
}