下面介绍模板类来实现双链表表和队列，由于队列是先进先出原则，所以可以通过调用双链表实现进队和出队等操作，Container<T>为“容器”，利用模板的模板参数--容器适配器调用双链表。

下面用模板实现了顺序表的头插、尾插、头删、尾删、逆置、排序、去重、合并两个链表及增删查改等操作。

如下所示：

#pragma once#include
     
      #include
      
       template
       
        struct ListNode{public:	ListNode(const T& x)		:_data(x)		, _prev(NULL)		, _next(NULL)	{}	T _data;	ListNode
        
         * _prev;	ListNode
         
          * _next;};template
          
           class List{public: List() :_head(NULL) , _tail(NULL) {} List(const List
           
            & s) :_head(NULL) , _tail(NULL) { ListNode
            
             * cur = s._head; while (cur) { this->PushBack(cur->_data); cur = cur->_next; } } List
             
              & operator=(List
              
               & s) { ListNode
               
                * cur = s._head; while (cur) { this->PushBack(cur->_data); cur = cur->_next; } swap(_head, s._head); swap(_tail, s._tail); return *this; } ~List() { ClearList(); }public: void PrintList()//打印双链表 { ListNode
                
                 * cur = _head; while (cur) { cout << cur->_data << "->"; cur = cur->_next; } cout << "NULL" << endl; } void ClearList()//释放所有节点 { ListNode
                 
                  * tmp = _head; while (tmp) { ListNode
                  
                   *del = tmp; tmp = tmp->_next; delete del; del = NULL; } } void PushBack(const T& x)//尾插 { if (_head == NULL) { _head = _tail = new ListNode
                   
                    (x); } else { ListNode
                    
                     * next = new ListNode
                     
                      (x); _tail->_next = next; next->_prev = _tail; _tail = next; _tail->_next = NULL; } } void PopBack()//尾删 { if (_head == _tail) { if (_head) { delete _tail; _head = _tail = NULL; } } else { ListNode
                      
                       * prev = _tail->_prev; delete _tail; prev->_next = NULL; _tail = prev; } } void PushFront(const T& x)//头插 { if (_head == NULL) { _head = _tail = new ListNode
                       
                        (x); } else { ListNode
                        
                         * cur = new ListNode
                         
                          (x); cur->_next = _head; _head->_prev = cur; _head = cur; } } void PopFront()//头删 { if (_head == _tail) { if (_head) { delete _head; _head = _tail = NULL; } } else  { ListNode
                          
                           * cur = _head->_next; delete _head; _head = cur; cur->_prev = NULL; } } ListNode
                           
                            * Find(const T& x)//查找x位置 { ListNode
                            
                             * cur = _head; while (cur) { if (x == cur->_data) { return cur; } cur = cur->_next; } return NULL; } void Insert(ListNode
                             
                              * pos,const T& x)//在pos位置处添加x {//注意考虑pos==_head时 assert(pos); if (pos == _head) { PushFront(x); } else { ListNode
                              
                               * prev = pos->_prev; ListNode
                               
                                * cur = new ListNode
                                
                                 (x); ListNode
                                 
                                  * next = pos; prev->_next = cur; cur->_prev = prev; cur->_next = next; next->_prev = cur; } } void Erase(ListNode
                                  
                                   * pos)//删除节点 {//注意考虑pos==_head，pos==_tail时 assert(pos); if (pos == _head) { PopFront(); } else if(pos == _tail) { PopBack(); } else { ListNode
                                   
                                    * prev = pos->_prev; ListNode
                                    
                                     * next = pos->_next; delete pos; prev->_next = next; next->_prev = prev; } } void Reverse()//逆置 { swap(_head, _tail); ListNode
                                     
                                      * cur = _head; while (cur) { swap(cur->_prev, cur->_next); cur = cur->_next; } } void Sort()//冒泡排序 { ListNode
                                      
                                       * tmp = NULL; while (tmp != _head->_next) { ListNode
                                       
                                        * cur = _head; ListNode
                                        
                                         * next = cur->_next; while (tmp != next) { if (cur->_data > next->_data) { swap(cur->_data, next->_data); } cur = cur->_next; next = next->_next; } tmp = cur;//tmp指向cur,即比较到某值处 } } void Unique()//去重，针对有序链表 { ListNode
                                         
                                          * cur = _head; ListNode
                                          
                                           * next = _head->_next; while (next) { while (cur->_data == next->_data) { ListNode
                                           
                                            * tmp = next; next = next->_next; Erase(tmp); } cur = cur->_next; next = next->_next; } } void Merge(List
                                            
                                             & l)//合并，相当将链表l追加在原链表后面 { _tail->_next = l._head; l._head->_prev = _tail; } void Splice(ListNode
                                             
                                              * pos, List
                                              
                                               & l)//某一链表插入到pos后面 { assert(pos); if (pos == _tail) { Merge(l); } else { ListNode
                                               
                                                * cur = pos; ListNode
                                                
                                                 * next = pos->_next; cur->_next = l._head; l._head->_prev = cur; next->_prev = l._tail; l._tail->_next = next; _tail->_next = NULL; } } size_t Size()//双链表的长度 { ListNode
                                                 
                                                  * cur = _head; size_t size = 0; while (cur) { size++; cur = cur->_next; } return size; }public: ListNode
                                                  
                                                   * _head; ListNode
                                                   
                                                    * _tail;};
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

   queue是容器配接器C的一个示例，容器配接器C将一些基础容器转换成类C的容器。容器配接器queue、stack、priority_queue——与标准模板库的其他处理是截然不同的。他们的方法和定义要调用基础容器类的方法。queue的基础类可以为list，list类中有size,empty,push_back,pop_front,front,back方法。deque类也可以作为基础类，而且是默认的基础类。vector类不能作为基础类，vector类没有pop_front方法。

函数列表：

empty() 如果队列空则返回真 

front() 返回第一个元素 

pop() 删除第一个元素 

push() 在末尾加入一个元素 

size() 返回队列中元素的个数

队列的实现入队、出队、判空、队头、队尾及队中元素个数等操作

template
     
      
       class Container=List>class Queue{public:	bool Empty()//判空	{		return _con.Size() == 0;	}	size_t Size()//求队列大小	{		return _con.Size();	}	T& Front()//求出队头元素	{		assert(_con._head);		return _con._head->_data;	}	T& Back()//求出队尾元素	{		assert(_con._tail);		return _con._tail->_data;	}	void PushBack(const T& x)//入队	{		_con.PushBack(x);	}	void PopFront()//出队	{		_con.PopFront();	}	void PrintQueue()	{		_con.PrintList();	}protected:	Container
       
         _con;};
       
      
     

双链表及队列的测试用例如下：

void Test1(){//尾插尾删	//List
     
       s1;	//s1.PushBack(1);	//s1.PushBack(2);	//s1.PushBack(3);	//s1.PrintList();	List
      
        s2;	s2.PushBack("xxxxxx");	s2.PushBack("yyyyyy");	s2.PushBack("zzzzzz");	s2.PrintList();	List
       
         s4(s2);	s4.PrintList();	List
        
          s3;	s3 = s2;	s3.PrintList();	//s2.PopBack();	//s2.PopBack();	//s2.PrintList();	//s2.PopBack();	//s2.PopBack();	//s2.PrintList();}void Test2(){//头插头删	List
         
           s1;	s1.PushFront(1);	s1.PushFront(2);	s1.PushFront(3);	s1.PrintList();	List
          
            s2; s2.PushFront("xxxxxx"); s2.PushFront("yyyyyy"); s2.PushFront("zzzzzz"); s2.PrintList(); s2.PopFront(); s2.PopFront(); s2.PrintList(); s2.PopFront(); s2.PopFront(); s2.PrintList();}void Test3(){//查找，增加，删除,逆置 List
           
             s; s.PushBack("xxxxxx"); s.PushBack("yyyyyy"); s.PushBack("zzzzzz"); s.PrintList(); s.Insert(s.Find("xxxxxx"), "ffffff"); s.PrintList(); s.Erase(s.Find("ffffff")); s.PrintList(); s.Reverse(); s.PrintList();}void Test4(){//冒泡排序，去重 List
            
              s1; s1.PushBack("yyyyyy"); s1.PushBack("zzzzzz"); s1.PushBack("xxxxxx"); List
             
               s2; s2.PushBack("qqqqqq"); s2.PushBack("ffffff"); s2.PushBack("ssssss"); s1.PrintList(); s2.PrintList(); s1.Sort(); s2.Sort(); s1.PrintList(); s2.PrintList(); List
              
                s3; s3.PushBack("yyyyyy"); s3.PushBack("qqqqqq"); s3.PushBack("zzzzzz"); s3.PushBack("xxxxxx"); s3.PushBack("qqqqqq"); s3.PushBack("xxxxxx"); s3.PushBack("xxxxxx"); s3.PushBack("ssssss"); s3.Sort(); s3.PrintList(); s3.Unique(); s3.PrintList();}void Test5(){//合并链表,某一链表插入到pos后面 List
               
                 s1; s1.PushBack("xxxxxx"); s1.PushBack("rrrrrr"); s1.PushBack("pppppp"); s1.PushBack("qqqqqq"); List
                
                  s2; s2.PushBack("wwwwww"); s2.PushBack("vvvvvv"); s2.PushBack("uuuuuu"); s1.Sort(); s1.PrintList(); s2.Sort(); s2.PrintList(); //s1.Merge(s2); //s1.PrintList(); //s1.Sort(); //s1.PrintList(); //s2._head->_prev = NULL; //s1._tail->_next = NULL; ListNode
                 
                  * pos = s1.Find("rrrrrr"); s1.Splice(pos, s2); s1.PrintList(); pos->_prev = NULL; pos->_next = NULL; s2._head->_prev = NULL; s2._tail->_next = NULL;}void Test6(){ //Queue
                  
                    s1; //s1.PushBack(1); //s1.PushBack(2); //s1.PushBack(3); //cout << s1.Empty() << endl; //cout << "Front->" << s1.Front() << endl; //cout << "Back->" << s1.Back() << endl; s1.PopFront(); s1.PrintQueue(); s1.PopFront(); s1.PopFront(); s1.PopFront(); s1.PrintQueue(); Queue
                   
                     s2; s2.PushBack("ssssss"); s2.PushBack("xxxxxx"); s2.PushBack("yyyyyy"); s2.PushBack("zzzzzz"); cout << s2.Empty() << endl; cout << "Size->" << s2.Size() << endl; cout << "Front->" << s2.Front() << endl; cout << "Back->" << s2.Back() << endl; string out = s2.Front(); //访问队列 while (!s2.Empty()) { cout << s2.Front() << "->"; s2.PopFront(); } cout << "NULL" << endl;}