使用List模拟实现STL中的Queue

queue单向队列与栈有点类似，一个是在同一端存取数据，另一个是在一端存入数据，另一端取出数据。单向队列中的数据是先进先出（First In First Out,FIFO）。在STL中，单向队列也是以别的容器作为底部结构，再将接口改变，使之符合单向队列的特性就可以了。因此实现也是非常方便的。下面就给出单向队列的函数列表和VS2008中单向队列的源代码。单向队列一共6个常用函数（front()、back()、push()、pop()、empty()、size()），与栈的常用函数较为相似。

成员函数

（1）T& back()

返回队列最后一个元素

（2）const T& back()const

返回队列最后一个元素

（3）bool empty()const

如果队列为空，返回true，否则返回为false

（4）T& front()

返回队列第一个元素

const T& front()const

返回队列第一个元素

（5）void pop()

移去队列中的第一个元素

（6）void push(const T& el)

在队列尾部插入元素el

（7）queue()

创建一个空队列

（8）size_type size()const

返回队列中元素数目

template<class T, class container = deque<T>>
class Queue
{
public:
    Queue()
    {}

    void Push(const T& s)
    {
        _con.push_back();
    }

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

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

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

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

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

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

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

private:
    container _con;
};

用list实现：

#include <iostream>
using namespace std;


#pragma once
template<class T>
struct ListNode
{
    ListNode(const T& data = T())
        : _prev()
        , _next()
        , _data(data)
    {}

    ListNode<T>* _prev;
    ListNode<T>* _next;
    T _data;
};


template<class T, class Ref, class Ptr>
class __ListIterator__
{
    typedef __ListIterator__<T, T&, T*> Iterator;
    typedef __ListIterator__<T, const T&, const T*> const_Iterator;
    typedef __ListIterator__<T, Ref, Ptr> Self;
    typedef ListNode<T>* LinkType;
    typedef Ref Reference;
    typedef Ptr Pointer;

public:
    __ListIterator__(LinkType x = ) //构造函数
        :_node(x)
    {}

    __ListIterator__(const Iterator& x)  //拷贝构造函数
        :_node(x._node)
    {}

    bool operator == (const Iterator& x)
    {
        return _node == x._node;
    }

    bool operator != (const Iterator& x)
    {
        return _node != x._node;
    }

    Reference operator * ()
    {
        return (*_node)._data;
    }

    Pointer operator -> ()
    {
        return &(operator*());
    }

    Self& operator ++ ()
    {
        _node = _node->_next;
        return *this;
    }

    Self operator ++ (int)
    {
        LinkType temp = _node;
        _node = _node->_next;
        return temp;
    }

    Self& operator -- ()
    {
        _node = _node->_prev;
        return *this;
    }

    Self operator -- (int)
    {
        LinkType temp(_node);
        _node = _node->_prev;
        return temp;
    }

public:
    LinkType _node;
};


template<class T>
class List
{
public:
    typedef ListNode<T> Node;
    typedef T ValueType;
    typedef ValueType& Reference;
    typedef const ValueType& const_Reference;
    typedef ValueType* Pointer;
    typedef const ValueType* const_Pointer;
    typedef Node* LinkType;
    typedef size_t size_type;
    typedef __ListIterator__<T, T&, T*> Iterator;
    typedef __ListIterator__<T, const T&, const T*> const_Iterator;

public:
    List()
    {
        EmptyInit();
    }

    List(size_type n, const T& data = T())  //构造n个数值为data的节点，并连接成一个链表
    {
        _node = new Node(data);
        LinkType NewNode = _node;

        while(n--)
        {
            NewNode->_next = new Node(data);
            NewNode->_prev = _node;
            NewNode->_next->_prev = NewNode;
            NewNode = NewNode->_next;
        }
        NewNode->_next = _node;
        _node->_prev = NewNode;
    }

    List(const List<T>& l)   //拷贝构造函数
    {
        EmptyInit();
        Iterator it = l._node->_next;  
        while(it != _node) 
        {  
            PushBack(*it);  
            ++it;  
        }
    }

    ~List()   //析构函数
    {
        if(_node != NULL)  
        { 
            cout<<"~List()"<<endl;
            delete _node;
            _node = NULL;         
        } 
    }

    List<T>& operator = (const List<T>& l)   //赋值运算符重载
    {
        if(this != &l)
        {
            Iterator temp(l._node);  
            Clear(); 
            delete _node;
            _node = temp._node;

        }
        return *this;
    }

    
    Iterator Begin()  //返回首元素之后位置的迭代器指针
    {
        return _node->_next;
    }

    const_Iterator Begin()const
    {
        return _node->_next;
    }

    Iterator End()  //返回尾元素之后位置的迭代器指针
    {
        return _node;
    }

    const_Iterator End()const
    {
        return _node;
    }

    bool Empty()  //判断链表是否为空
    {
        return _node == _node->_next;
    }

    size_type Size()const   //返回链表c中实际元素的个数
    {
        size_type size = ;
        Iterator it(_node->_next);
        while(it != _node)
        {
            ++size;
            ++it;
        }
        return size;
    }

    size_type MaxSize()const  //返回链表c可能容纳的最大元素数量
    {
        return size_type(-);
    }

    Reference Front()   //返回首元素的引用
    {
        return *(Begin());
    }

    const_Iterator Front()const
    {
        return *(Begin());
    }

    Reference Back() // 返回尾元素的引用 
    {
        return *(End()-);
    }

    const_Reference Back()const
    {
        return *(End()-);
    }

    Iterator Insert(Iterator pos, const T& x = T()) //在迭代器指针it前插入元素x,返回x迭代器指针
    {
        LinkType temp = new Node(x);
        temp->_next = pos._node;
        temp->_prev = pos._node->_prev;
        pos._node->_prev = temp;
        temp->_prev->_next = temp;
        return temp;
    }

    void PushFront(const T& x)  //list元素首元素前添加一个元素X
    {
        Insert(Begin(), x);
    }

    void PushBack(const T& x)   //list元素尾元素添加一个元素X
    {
        Insert(End(), x);
    }

    Iterator Erase(Iterator pos)   //删除迭代器指针it对应的元素
    {
        LinkType _nextNode = pos._node->_next;
        LinkType _preNode = pos._node->_prev;

        _nextNode->_prev = _preNode;
        _preNode->_next = _nextNode;
        delete pos._node;
        return _nextNode;
    }

    void PopFront() //删除容器首元素，当且仅当容器不为空
    {
        Erase(Begin());
    }

    void PopBack()  //删除容器尾元素，当且仅当容器不为空
    {
        Iterator Del = End();
        Erase(--Del);
    }

    void ReSize(size_type newSize, const T& value = ) //从新定义链表的长度,超出原始长度部分用num代替,小于原始部分删除。
    {
        if(newSize < Size())
        {
            size_type size = Size() - newSize;

            while(size--)
            {
                PopBack();
            }
        }
        else
        {
            size_t count = newSize - Size();

            while(count)
            {
                size_type size = Size();
                Iterator temp = _node;

                PushBack(value);
                count--;
            }
        }
    }

    void Assign(size_type n, const T& data)
    {
        Iterator pTemp = _node->_next;
        if(Size()>=n)
        {
            for(size_t idx=;idx<n; ++idx)
            {
                pTemp._node->_data = data;
                ++pTemp;
            }
            for(size_t idx = ; idx<Size()-n; ++idx)
            {
                PopBack();
            }
        }
        else
        {
            pTemp = _node->_next;
            size_t size = Size();
            for(size_t idx=; idx<size; ++idx)
            {
                pTemp._node->_data = data;
                ++pTemp;
            }
            for(size_t idx = ;idx<n-size; ++idx)
            {
                PushBack(data);
            }
        }
        _node = new Node(data);
        LinkType NewNode = _node;

    }

    void Clear()  //删除容器中的所有元素
    {
        Iterator it = Begin();
        while(it != End())
        {
            it = Erase(it);
        }
    }

private:
    void EmptyInit()
    {
        _node = new Node;
        _node->_prev = _node;
        _node->_next = _node;
    }

public:
    LinkType _node;
};

//Stack栈的模板类的实现
template<class T,class Con = Vector<T> >
class Stack
{
public:
    typedef size_t SizeType;
    typedef T ValueType;

public:
    Stack()
    {}

    //判空
    bool Empty()
    {
        return (_con.Size()==);
    }
    void Push(const ValueType data)
    {
        _con.PushBack(data);
    }

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

    SizeType Size()const
    {
        return _con.Size();
    }

    ValueType& Top()
    {
        return _con.Back();
    }

    const ValueType& Top()const
    {
        return _con.Back();
    }
private:
    Con _con;
};

使用List模拟实现STL中的Queue

继续阅读

面试题:vector和map的区别，异同。空间分布，100万数据存哪个比较合适。一、迭代器区别二、vector三、Map、Set四、vector_map 为什么比map效率高五、如何选择六、容器选择原则七、效率对比

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

成员函数初始化列表

2021-08-13c++——类之操作符重载

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

Linux设备模型（中）之上层容器