基于List实现适配器queue(链式队列)

队列遵循先进先出，后进后出的原则，它有两个出口，从最底端加入元素、取得最顶端的元素。实现队列我们通常建立在链表的基础上。下来我们利用之前实现过的容器List中的一部分接口来实现queue
（在这里分别用了模板参数和模板的模板参数两种方式来实现来实现）

queue.h

#pragma once
#include "List.h"

//模板参数
template<class T,class Container=List<T>>
class Queue1
{
public:
    Queue1()
    {}
    void Push(const T& data)
    {
        s.PushBack(data);
    }
    void Pop()
    {
        s.PopFront();
    }
    bool Empty()
    {
        return s.Empty();
    }
    size_t Size()
    {
        return s.Size();
    }
    T& Front()
    {
        return s.Front();
    }
    const T& Front()const
    {
        return s.Front();
    }
    T& Back()
    {
        return s.Back();
    }
    const T& Back()const
    {
        return s.Back();
    }
private:
    List<T> s;
};

//模板的模板参数
template<class T, template<class> class Container = List>
class Queue2
{
public:
    Queue2()
    {}
    void Push(const T& data)
    {
        s.PushBack(data);
    }
    void Pop()
    {
        s.PopFront();
    }
    bool Empty()
    {
        return s.Empty();
    }
    size_t Size()
    {
        return s.Size();
    }
    T& Front()
    {
        return s.Front();
    }
    const T& Front()const
    {
        return s.Front();
    }
    T& Back()
    {
        return s.Back();
    }
    const T& Back()const
    {
        return s.Back();
    }
private:
    List<T> s;
};

List.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdlib.h>
#include <iostream>
using namespace std;


template<class T>
struct ListNode
{
    ListNode(const T& data = T())
    : _pPre(0)
    , _pNext(0)
    , _data(data)
    {}

    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _data;
};

template<class T,class Ref,class Ptr>
class ListIterator
{
    typedef ListIterator<T, Ref, Ptr> Self;
public:
    ListIterator()
        :_pCur(0)
    {}

    ListIterator(ListNode<T>* pCur)
        : _pCur(pCur)
    {}

    ListIterator(const Self& s)
        : _pCur(s._pCur)
    {}

    Ref operator*()
    {
        return _pCur->_data;
    }

    Ptr operator->()
    {
        return &(operator*());
        //return &(_pCur->_data); 
    }

    Self& operator++()
    {
        _pCur = _pCur->_pNext;
        return*this;
    }

    Self operator++(int)
    {
        Self temp(*this);
        _pCur = _pCur->_pNext;
        return temp;
    }

    Self& operator--()
    {
        _pCur = _pCur->_pPre;
        return*this;
    }

    Self operator--(int)
    {
        Self temp(*this);
        _pCur = _pCur->_pPre;
        return temp;
    }

    bool operator!=(const Self& s)
    {
        return _pCur != s._pCur;
    }

    bool operator==(const Self& s)
    {
        return _pCur == s._pCur;
    }

    ListNode<T>* _pCur;
};

template <class T>
class List
{
public:
    typedef ListIterator<T, T&, T*> Iterator;
    typedef ListNode<T> Node;
public:
    List()
        : _pHead(new Node)
    {
        _pHead->_pNext = _pHead;//带头节点的循环链表
        _pHead->_pPre = _pHead;
    }

    // 1 2 3 4 5 
    List(const T* array, size_t size)
        :_pHead(new Node)
    {
        _pHead->_pNext = _pHead;
        _pHead->_pPre = _pHead;
        for (size_t i = 0; i < size; i++)
        {
            PushBack(array[i]);
        }
    }
    List(const List<T>& l)
        :_pHead(new Node)
    {
        _pHead->_pNext = _pHead;
        _pHead->_pPre = _pHead;
        Node* cur = l._pHead->_pNext;
        for (size_t i = 0; i < l.Size();i++)
        {
            PushBack(cur->_data);
            cur = cur->_pNext;
        }

    }
    List<T>& operator=(const List<T>& l)
    {
        if (this != &l)
        {
            Node* pRet = l._pHead->_pNext;
            for (size_t i = 0; i < l.Size(); i++)
            {
                PushBack(pRet->_data);
                pRet = pRet->_pNext;
            }
        }
        return *this;
    }
    ~List()
    {
        Clear();
        delete _pHead;
        _pHead = NULL;
    }

        ///////////////////////////////////////////////////// 
    Iterator Begin()
    {
        return Iterator(_pHead->_pNext);
    }

    Iterator End()
    {
        return Iterator(_pHead);
    }
    /////////////////////Modify////////////////////////// 
    void PushBack(const T& data)
    {
        Node* _pNewNode = new Node(data);
        if (Empty())//链表为空
        {
            _pHead->_pNext = _pNewNode;
            _pHead->_pPre = _pNewNode;
            _pNewNode->_pNext = _pHead;
            _pNewNode->_pPre = _pHead;
        }
        else
        {
            Node* pTail = _pHead->_pPre;
            pTail->_pNext = _pNewNode;
            _pNewNode->_pNext = _pHead;
            _pNewNode->_pPre = pTail;
            _pHead->_pPre = _pNewNode;
        }
    }
    void PopBack()
    {
        if (Empty())//链表为空
        {
            return;
        }
        else
        {
            Node* del = _pHead->_pPre;//要删除的节点
            Node* tail = del->_pPre;//新的尾节点
            delete del;
            tail->_pNext = _pHead;
            _pHead->_pPre = tail;
        }
    }
    void PushFront(const T& data)
    {
        Node* _pNewNode = new Node(data);
        _pHead->_pNext->_pPre = _pNewNode;
        _pNewNode->_pNext = _pHead->_pNext;
        _pNewNode->_pPre = _pHead;
        _pHead->_pNext = _pNewNode;
    }
    void PopFront()
    {
        if (Empty())
        {
            return;
        }
        else
        {
            Node* pDel = _pHead->_pNext;
            _pHead->_pNext = pDel->_pNext;
            pDel->_pNext->_pPre = _pHead;
            delete pDel;
        }
    }
    Iterator Insert(Iterator pos, const T& data)
    {
        Node* _pNewNode = new Node(data);
        pos._pCur->_pPre->_pNext = _pNewNode;
        _pNewNode->_pNext = pos._pCur;
        _pNewNode->_pPre = pos._pCur->_pPre;
        pos._pCur->_pPre = _pNewNode;
        return Iterator(_pNewNode);
    }
    Iterator Erase(Iterator pos)
    {
        Node* pCur = pos._pCur->_pNext;
        pos._pCur->_pNext->_pPre = pos._pCur->_pPre;
        pos._pCur->_pPre->_pNext = pos._pCur->_pNext;
        delete pos._pCur;
        return Iterator(pCur);
    }
    Iterator Find(const T& d)        //通过迭代器来查找
    {
        Iterator it = Begin();
        while (it != End())
        {
            if ((*it) == d)
                return it;
            it++;
        }
        return End();
    }
    bool Empty()const
    {
        return _pHead->_pNext == _pHead;
    }
    size_t Size()const
    {
        Node* pCur = _pHead->_pNext;
        size_t count = 0;
        while (pCur != _pHead)
        {
            ++count;
            pCur = pCur->_pNext;
        }
        return count;
    }
    T& Front()
    {
        return _pHead->_pNext->_data;
    }
    const T& Front()const
    {
        return _pHead->_pNext->_data;
    }
    T& Back()
    {
        return _pHead->_pPre->_data;
    }
    const T& Back()const
    {
        return _pHead->_pPre->_data;
    }
    void Clear()
    {
        Iterator it = Begin();
        while (it != End())
        {
            it = Erase(it);
        }
        _pHead->_pNext = _pHead;
        _pHead->_pPre = _pHead;
    }
private:
    ListNode<T>* _pHead;
};
void PrintList( List<int>& l)
{
    List<int>::Iterator It = l.Begin();
    while (It != l.End())
    {
        cout << *It << " ";
        ++It;
    }
    cout << endl;
}

测试代码

#define _CRT_SECURE_NO_WARNINGS 1

#include "queue.h"

void FunTest1()
{
    Queue1<int, List<int>> q1;
    for (int i = 0; i <= 5; i++)
    {
        q1.Push(i);
    }
    while (!q1.Empty())
    {
        cout << q1.Front() << " ";
        q1.Pop();
    }
    cout << endl;
}
void FunTest2()
{
    Queue2<int, List> q2;
    for (int i = 0; i <= 5; i++)
    {
        q2.Push(i);
    }
    while (!q2.Empty())
    {
        cout << q2.Front() << " ";
        q2.Pop();
    }
    cout << endl;
}
int main()
{
    FunTest1();
    FunTest2();
    system("pause");
    return 0;
}

读者可以自己进行跟踪调试查看结果