适配器：
将一个通用的容器转换为另外的容器，所谓的容器，指的是存放数据的器具，像我们知道的顺序表和链表都是容器Container。举个例子解释一下吧，我们的电压都是220v,而像充电线就起到转换到合适的电压的作用。而这里，我们的主角就是将通用的链表结构转换为来实现队列Queue这一数据结构，（意思就是，链表还可以去实现其他的数据结构）。
在线性表中，分为链表和顺序表，我们知道其中的差别：
链表：节点灵活，使得插入删除元素方便灵活，但是对于单链表若有节点指针_head、_tail，查找元素较为麻烦，需要遍历。
顺序表：开辟一块连续的内存空间，查找元素方便，通过指针或者下标来访问。插入或者删除元素呢，又较为复杂，插入时需要将后面的元素挨着挨着全部后移，删除元素后又需要将后面的元素全部前移。
针对队列Queue模型，我们知道它是尾插头删、先进先出的特点。因此我针对以上原因选用链表结构来实现队列Queue。可以参照下图：
代码如下：
#include<iostream>using namespace std;
#include<assert.h>
template<class T>
struct ListNode
{
ListNode(const T& x)
:_next(NULL)
, _prev(NULL)
, _data(x)
{}
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
};
template<class T>
class List
{
public:
List()
:_head(NULL)
, _tail(NULL)
{}
List(const List<T>& l)
{
ListNode<T>* cur = l._head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
List<T>& operator=(const List<T>& l)
{
//先删除节点，再插入节点
if (&s != this)
{
ListNode<T>* pcur = _head;
while (pcur)
{
ListNode<T>* del = pcur;
pcur = pcur->_next;
delete del;
del = NULL;
}
ListNode<T>* cur = _head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
return *this;
}
~List()//一个节点一个节点的删除
{
ListNode<T>* cur = _head;
while (cur)
{
ListNode<T>* del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
}
void PushBack(const T& x);
void PopBack();
void PopFront();
void PrintList();
void Reverse();
size_t Length();
public:
ListNode<T>* _head;
ListNode<T>* _tail;
};
//尾插
template<class T>
void List<T>::PushBack(const T& x)
{
//分析：分为两种情况：无节点、有节点
if (_head == NULL)
{
_head = _tail = new ListNode<T>(x);
}
else
{
ListNode<T>* cur = new ListNode<T>(x);
_tail->_next = cur;
cur->_prev = _tail;
_tail = cur;
_tail->_next = NULL;
}
}
//尾删
template<class T>
void List<T>::PopBack()
{
//分析：分为三种情况：无节点、一个节点、多个节点
if (_head == _tail)
{
if (_head == NULL)
{
return;
}
else
{
delete _head;
_head = _tail = NULL;
}
}
else
{
ListNode<T>* prev = _tail->_prev;
delete _tail;
_tail = NULL;
_tail = prev;
_tail->_next = NULL;
}
}
//头删
template<class T>
void List<T>::PopFront()
{
if (_head == _tail)
{
if (_head == NULL)
{
return;
}
delete _head;
_head = _tail = NULL;
}
else
{
ListNode<T>* cur = _head;
ListNode<T>* del = _head;
_head = cur->_next;
delete del;
del = NULL;
_head->_prev = NULL;
}
}
//逆置
template<class T>
void List<T>::Reverse()
{
//分析：从两头开始走,交换数据（分奇数个数据和偶数个数据）
ListNode<T>* begin = _head;
ListNode<T>* end = _tail;
while (!((begin == end) || end->_next == begin))
{
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}
}
//长度
template<class T>
size_t List<T>::Length()
{
ListNode<T>* cur = _head;
int count = 0;
while (cur)
{
++count;
cur = cur->_next;
}
return count;
}
//打印
template<class T>
void List<T>::PrintList()
{
ListNode<T>* cur = _head;
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
template<class T, template<class> class Container = List> //缺省形式
class Queue
{
public:
//入队
void Push(const T& x)
{
_con.PushBack(x);
}
//出队
void Pop()
{
_con.PopFront();
}
//大小
size_t Size()
{
return _con.Length();
}
//判空
bool Empty()
{
return Size() == 0;
}
//队头
T& Front()
{
size_t size = Size();
assert(size > 0);
return _con._head->_data;
}
//队尾
T& Back()
{
size_t size = Size();
assert(size > 0);
return _con._tail->_data;
}
protected:
Container<T> _con;
};
//队列的测试函数
void TestQueue()
{
Queue<int, List> q1;
//Queue<int> q1;
q1.Push(1);
q1.Push(2);
q1.Push(3);
q1.Push(4);
q1.Push(5);
//访问队列所有元素(队列是插尾删头)
while (!q1.Empty())
{
cout<< q1.Front() << " ";
q1.Pop();
}
}
int main()
{
TestQueue();
system("pause");
return 0;
}
本文出自 “Han Jing's Blog” 博客，请务必保留此出处http://10740184.blog.51cto.com/10730184/1751682