43_迭代器、栈、队列

迭代抽象

  1. 表示某个数据
  2. 数据成员:元素指针
  3. 成员函数:下一个(++),获取数据(*),逻辑运算(!= == )等等
  4. const迭代器一般只能遍历,不提供修改。
  5. 模板带有作用域定义声明一起实现
  6. 解决了节点的安全隐患

链表时间复杂度

  1. 插入O(1)
  2. 删除O(1)
  3. 查询O(n)
  4. 随机访问O(n)

使用场合

  1. 插入和删除频繁的场景
  2. 游戏里面的场景,怪物刷新和死亡

栈和队列

  1. 栈先进后出,后进先出
  2. 队列是先进先出,后进后出

  1. 一般用单向链表来做
  2. 栈一般提供迭代器

队列

  1. 一般提供单向链表来做

使用数组存放栈和队列的时候

提前知道空间多大的时候

作业

1.数组模板增加迭代器

 //Vector.h
#pragma once

template 
class CVector
{
public:
    class Iterator  //类内部迭代器
    {
    public:
        Iterator(T *element = nullptr)
        {
            m_pElement = element;
        }
        
        T& operator*()
        {
            return *m_pElement;
        }

        Iterator operator++()
        {
            m_pElement++;
        }

        Iterator operator++(int)
        {
            Iterator pOldIteraotr = Iterator(m_pElement);
            m_pElement++;
            return pOldIteraotr;
        }

        bool operator==(Iterator& it)
        {
            return m_pElement == it.m_pElement;
        }

        bool operator!=(Iterator& it)
        {
            return m_pElement != it.m_pElement;
        }

    private:
        T *m_pElement;
    };
public:
    CVector(const unsigned initCapacity = 1U)    //默认构造二个,其它构造为2倍
    {
        m_pElement = new T[initCapacity * 2];
        setSize(0U);
        setCapacity(initCapacity * 2);
    }

    CVector(const CVector& obj) //采用深拷贝,新的向量不会影响当前向量
    {
        m_pElement = new T[obj.getSize() * 2];

        for (unsigned i = 0; i < obj.getSize(); i++)
        {
            m_pElement[i] = obj.m_pElement[i];
        }

        setSize(obj.getSize());
        setCapacity(getSize() * 2);
    }

    CVector(CVector&& obj) //移动构造
    {
        setCapacity(obj.getSize());
        setSize(obj.getSize());
        m_pElement = obj.m_pElement;
        obj.m_pElement = nullptr;
    }

    ~CVector()
    {
        if (m_pElement != nullptr)
        {
            delete[] m_pElement;
        }
    }

    const bool isEmpty() const  //判断使用的空间是否为空,给用户提供判空方法
    {
        if (m_uSize != 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    CVector& push_back(const T& element)    //末尾添加元素
    {
        checkCapacity();
        //存放数据
        *(m_pElement + getSize()) = element;
        //设置使用的空间
        setSize(getSize() + 1U);
        return *this;
    }
    
    CVector& push_back(T&& element)
    {
        checkCapacity();
        //存放数据
        *(m_pElement + getSize()) = element;
        //设置使用的空间
        setSize(getSize() + 1U);
        //置空以前的
        element = NULL;
        return *this;
    }
    

    CVector& pop_back() //末尾删除元素
    {
        //如果实际使用空间不为0
        if (getSize() != 0U)
        {
            setSize(getSize() - 1U);
        }

        return *this;
    }

    T& operator[](const int index) throw(...)   //重载下标获得值
    {
        if (!isEmpty())
        {
            return *(m_pElement + index);
        }
        else
        {
            throw 0;
        }
    }

    CVector& insert(const int pos, const T& obj)     //向指定位置增加元素
    {
        checkCapacity();
        //从后面元素移动到下一个元素移动以前的数据
        for (int i = (getSize() - 1); i >= pos; i--)
        {
            m_pElement[i + 1] = m_pElement[i];
        }
        //插入数据
        m_pElement[pos] = obj;
        //设置使用的空间
        setSize(getSize() + 1U);

        return *this;
    }

    CVector& insert(const int pos, T&& obj)     //向指定位置增加元素
    {
        checkCapacity();
        //从后面元素移动到下一个元素移动以前的数据
        for (int i = (getSize() - 1); i >= pos; i--)
        {
            m_pElement[i + 1] = m_pElement[i];
        }
        //插入数据
        m_pElement[pos] = obj;
        //以前的置空
        obj = (T)NULL;
        //设置使用的空间
        setSize(getSize() + 1U);

        return *this;
    }

    CVector& earse(const int pos)  //删除指定位置元素
    {
        if (getSize() > 0)
        {
            //从后面元素移动到下一个元素移动以前的数据
            for (int i = pos; i < (int)getSize() - 1; i++)
            {
                m_pElement[i] = m_pElement[i + 1];
            }
            //设置使用的空间
            setSize(getSize() - 1U);
        }
        return *this;
    }

    void notChange()    //暂时不修改大小了,把实际占用空间和使用的空间设为一样
    {
        if (getSize() == 0U && getCapacity() != 0U)
        {
            delete[] m_pElement;
            setCapacity(0U);
            m_pElement = nullptr;
        }
        else if (getSize() != getCapacity())
        {
            T *pOldElement = m_pElement;
            m_pElement = new T[getSize()];
            for (unsigned i = 0; i < getSize(); i++)
            {
                m_pElement[i] = pOldElement[i];
            }
            delete[] pOldElement;

            setCapacity(getSize());
        }
    }

    void clear()    //清空元素
    {
        setSize(0U);
    }

    CVector& operator+(const CVector& obj)  //合并两个向量
    {
        //复制数据
        CVector *pVec = new CVector((this->getSize() + obj.getSize()) * 2);
        unsigned vec = 0;
        for (unsigned i = 0; i < this->getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = this->m_pElement[i];
        }
        for (unsigned i = 0; i < obj.getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = obj.m_pElement[i];
        }
        //设置空间
        pVec->setCapacity((vec - 1u) * 2);
        pVec->setSize(vec - 1u);
        return *pVec;
    }

    CVector& operator+(CVector&& obj)  //合并两个向量
    {
        //复制数据
        CVector *pVec = new CVector((this->getSize() + obj.getSize()) * 2);
        unsigned vec = 0;
        for (unsigned i = 0; i < this->getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = this->m_pElement[i];
        }
        for (unsigned i = 0; i < obj.getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = obj.m_pElement[i];
        }
        //设置空间
        pVec->setCapacity((vec - 1u) * 2);
        pVec->setSize(vec - 1u);
        //以前的置空
        obj.clear();
        obj.m_pElement = nullptr;
        obj.setCapacity(0U);
        return *pVec;
    }

    Iterator back()
    {
        return m_pElement + getSize();
    }

    Iterator front()
    {
        return m_pElement;
    }

    CVector& operator+= (CVector& vec)
    {
        for (int i = 0; i < vec.getSize(); i++)
        {
            push_back(vec[i]);
        }

        return *this;
    }
    
    CVector& operator+= (CVector&& vec)
    {
        for (int i = 0; i < vec.getSize(); i++)
        {
            push_back(vec[i]);
        }
        
        vec.clear();
        vec.m_pElement = nullptr;
        vec.setCapacity(0U);

        return *this;
    }


    unsigned getSize() const    //获取使用的空间
    {
        return m_uSize;
    }

    unsigned getCapacity() const    //获取实际占用空间
    {
        return m_uCapacity;
    }

private:
    void setSize(const unsigned size)   //设置使用的空间
    {
        m_uSize = size;
    }

    void setCapacity(const unsigned capacity)   //设置实际占用空间
    {
        m_uCapacity = capacity;
    }

    void checkCapacity()    //判断空间能否增加元素
    {
        //如果空间不够增加
        if (getSize() == getCapacity())
        {
            //设置旧的元素指针
            T *pOldElement = m_pElement;
            //设置实际存储空间为当前值的两倍
            setCapacity(getCapacity() * 2U);
            //申请新的占用空间
            m_pElement = new T[getCapacity()];
            //拷贝旧数据
            for (unsigned i = 0; i < getSize(); i++)
            {
                m_pElement[i] = pOldElement[i];
            }
            //清理掉以前的元素类型
            delete[] pOldElement;
        }
    }
private:
    T *m_pElement;      //存储的元素
    unsigned m_uSize;       //使用的空间
    unsigned m_uCapacity;   //实际占用空间
};

2.链表模板增加迭代器

 //LinkList.h
#pragma once
#include 
using namespace std;

template 
class CLinkList //双向链表类
{

private:
    class LinkNode //双向链表结点
    {
    public:
        LinkNode(T element = (T)0, LinkNode *previousNode = nullptr, LinkNode *nextNode = nullptr)
        {
            m_pElement = new T(element);
            m_pPreviousNode = previousNode;
            m_pNextNode = nextNode;
        }

        LinkNode::~LinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T *m_pElement;
        LinkNode *m_pPreviousNode;
        LinkNode *m_pNextNode;
    };

public:
    class Iterator
    {
    public:
        Iterator(LinkNode *node = nullptr)
        {
            m_pElement = node;
        }

        T& operator*()
        {
            return *(m_pElement->m_pElement);
        }

        Iterator& operator++()
        {
            m_pElement = m_pElement->m_pNextNode;

            return *this;
        }

        Iterator& operator++(const int)
        {
            Iterator *pIteratorOld = this;

            m_pElement = m_pElement->m_pNextNode;

            return *pIteratorOld;
        }

        bool operator== (const Iterator& it)
        {
            return m_pElement == it.m_pElement;
        }

        bool operator!= (const Iterator& it)
        {
            return m_pElement != it.m_pElement;
        }
    private:
        LinkNode* m_pElement;
    };

public:
    CLinkList()
    {
        m_pHeadNode = new LinkNode();                    //头结点
        m_pTailNode = new LinkNode();                    //尾结点
        m_pHeadNode->m_pNextNode = m_pTailNode;             //设置头结点
        m_pTailNode->m_pPreviousNode = m_pHeadNode;         //设置尾结点
        setSize(0U);                                        //大小为一
    }

    CLinkList(T& element)                                                  //带参构造
    {
        LinkNode *pNewNode = new LinkNode(element); //创建的新结点
        m_pHeadNode = new LinkNode(T(0));    //头结点
        m_pTailNode = new LinkNode(T(0));    //尾结点                                         
        m_pHeadNode->m_pNextNode = pNewNode;    //设置头结点    
        pNewNode->m_pPreviousNode = m_pHeadNode;    //设置新结点
        pNewNode->m_pNextNode = m_pTailNode;
        m_pTailNode->m_pPreviousNode = pNewNode; //设置尾结点
        setSize(1U);    //大小为一
    }

    CLinkList(T&& element)                                                 //移动带参构造
    {
        LinkNode *pNewNode = new LinkNode(element); //创建的新结点
        m_pHeadNode = new LinkNode(T(0));    //头结点
        m_pTailNode = new LinkNode(T(0));    //尾结点                                         
        m_pHeadNode->m_pNextNode = pNewNode;    //设置头结点    
        pNewNode->m_pPreviousNode = m_pHeadNode;    //设置新结点
        pNewNode->m_pNextNode = m_pTailNode;
        m_pTailNode->m_pPreviousNode = pNewNode; //设置尾结点
        setSize(1U);    //大小为一
        element = NULL;
    }
    
    CLinkList(const CLinkList& obj)                                        //拷贝构造
    {
        m_pHeadNode = new LinkNode();    //头结点
        m_pTailNode = new LinkNode();    //尾结点
        m_pHeadNode->m_pNextNode = m_pTailNode; //设置头结点
        m_pTailNode->m_pPreviousNode = m_pHeadNode; //设置尾结点
                                                    //拷贝的链表非空链表
        if (!obj.empty())
        {
            LinkNode *pNode = obj.m_pHeadNode->m_pNextNode;
            while (pNode->m_pNextNode != nullptr)
            {
                push_back(*(pNode->m_pElement));
                pNode = pNode->m_pNextNode;
            }
        }
        setSize(obj.getSize()); //设置大小
    }

    CLinkList(CLinkList&& obj)                                             //移动拷贝构造
    {
        m_pHeadNode = obj.m_pHeadNode;
        m_pTailNode = obj.m_pTailNode;
        setSize(obj.getSize());

        obj.m_pHeadNode = nullptr;
        obj.m_pTailNode = nullptr;
        obj.setSize(0U);
    }

    ~CLinkList()
    {
        clear();
        delete m_pHeadNode;
        delete m_pTailNode;
    }

    const unsigned getSize() const                                         //获取链表大写
    {
        return m_uSize;
    }
    
    void push_back(const T& element)                                       //尾结点增加元素
    {
        LinkNode *pNode = new LinkNode(element);
        //设置当前结点的前驱与后继
        pNode->m_pPreviousNode = m_pTailNode->m_pPreviousNode;
        pNode->m_pNextNode = m_pTailNode;
        //设置尾结点的前驱结点的后继为当前结点
        m_pTailNode->m_pPreviousNode->m_pNextNode = pNode;
        //设置尾节点的前驱
        m_pTailNode->m_pPreviousNode = pNode;
        setSize(getSize() + 1U);
    }

    void push_back(T&& element)                                            //尾结点移动增加元素
    {
        push_back(element);
        element = NULL;
    }

    void push_front(const T& element)                                      //头节点增加元素
    {
        LinkNode *pNode = new LinkNode(element);
        //设置当前结点的前驱与后继
        pNode->m_pPreviousNode = m_pHeadNode;
        pNode->m_pNextNode = m_pHeadNode->m_pNextNode;
        //设置头结点的后继结点的前继为当前结点
        m_pHeadNode->m_pNextNode->m_pPreviousNode = pNode;
        //设置头节点的后继
        m_pHeadNode->m_pNextNode = pNode;
        setSize(getSize() + 1U);
    }

    void push_front(T&& element)                                           //头节点移动增加元素
    {
        push_front(element);
        element = NULL;
    }

    Iterator* insert(LinkNode* pos, const T& element)                //指定结点前增加元素
    {
        LinkNode *pNode = new LinkNode(element);

        //设置新结点
        pNode->m_pPreviousNode = pos->m_pPreviousNode;
        pNode->m_pNextNode = pos;
        //设置旧结点的前继结点
        pos->m_pPreviousNode->m_pNextNode = pNode;
        //设置旧结点
        pos->m_pPreviousNode = pNode;
        setSize(getSize() + 1U);
        return pNode;
    }
    Iterator* insert(LinkNode* pos, T&& element)                     //指定结点前移动增加元素
    {
        LinkNode *pNode = new LinkNode(element);

        //设置新结点
        pNode->m_pPreviousNode = pos->m_pPreviousNode;
        pNode->m_pNextNode = pos;
        //设置旧结点的前继结点
        pos->m_pPreviousNode->m_pNextNode = pNode;
        //设置旧结点
        pos->m_pPreviousNode = pNode;
        setSize(getSize() + 1U);
        element = NULL;
        return pNode;
    }

    const bool empty() const                                               //是否空链表
    {
        if (getSize() != 0U)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    void clear()                                                           //清空表
    {
        if (!empty())
        {
            LinkNode *pNowNode = m_pHeadNode->m_pNextNode;
            LinkNode *pNextNode = nullptr;

            while (pNowNode->m_pNextNode != nullptr)
            {
                pNextNode = pNowNode->m_pNextNode;
                delete pNowNode;
                pNowNode = pNextNode;
            }

            m_pHeadNode->m_pNextNode = m_pTailNode;
            m_pTailNode->m_pPreviousNode = m_pHeadNode;
            setSize(0U);
        }
    }

    void erese(LinkNode* pos)                                  //删除指定位置的元素
    {
        if (!empty())
        {
            pos->m_pPreviousNode->m_pNextNode = pos->m_pNextNode;
            pos->m_pNextNode->m_pPreviousNode = pos->m_pPreviousNode;
            setSize(getSize() - 1U);
            delete pos;
        }
    }

    void pop_back()                                                        //删除最后一个元素
    {
        if (!empty())
        {
            LinkNode *pNode = m_pTailNode->m_pPreviousNode;
            pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
            pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
            setSize(getSize() - 1U);
            delete pNode;
        }
    }

    void pop_front()                                                       //删除第一个元素
    {
        if (!empty())
        {
            LinkNode *pNode = m_pHeadNode->m_pNextNode;
            pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
            pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
            setSize(getSize() - 1U);
            delete pNode;
        }
    }

    Iterator back()                                            //获得最后一个元素
    {
        if (!empty())
        {
            LinkNode *pNode = m_pTailNode;
            return pNode;
        }
        else
        {
            return nullptr;
        }
    }

    Iterator front()                                                   //获得最第一个元素
    {
        if (!empty())
        {
            LinkNode *pNode = m_pHeadNode->m_pNextNode;
            return pNode;
        }
        else
        {
            return nullptr;
        }
    }

    CLinkList& operator= (const CLinkList& list)                        //拷贝链表
    {
        CLinkList *pLink = new CLinkList;
        CLinkList *pOldLink = this;

        if (!list.empty())
        {
            this->~CLinkList();
            LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
            while (pNode->m_pNextNode != nullptr)
            {
                pLink->push_back(*(pNode->m_pElement));
                pNode = pNode->m_pNextNode;
            }
        }
        pLink->setSize(list.getSize());

        pOldLink->m_pHeadNode = pLink->m_pHeadNode;
        pOldLink->m_pTailNode = pLink->m_pTailNode;

        return *pLink;
    }

    CLinkList& operator= (CLinkList&& list)                             //移动拷贝链表
    {
        this->~CLinkList();

        m_pHeadNode = list.m_pHeadNode;
        m_pTailNode = list.m_pTailNode;
        setSize(list.getSize());

        list.m_pHeadNode = nullptr;
        list.m_pTailNode = nullptr;
        list.setSize(0U);

        return *this;
    }

    void operator+= (const CLinkList& list)                             //合并另一个链表到当前链表
    {
        if (!list.empty())
        {
            LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
            while (pNode->m_pNextNode != nullptr)
            {
                push_back(*(pNode->m_pElement));
                pNode = pNode->m_pNextNode;
            }
        }
    }

    void operator+= (CLinkList&& list)                                  //移动合并另一个链表到当前链表
    {
        if (!list.empty())
        {
            LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
            while (pNode->m_pNextNode != nullptr)
            {
                push_back(*(pNode->m_pElement));
                pNode = pNode->m_pNextNode;
            }

            list.clear();
        }

        delete list.m_pHeadNode;
        delete list.m_pTailNode;

        list.m_pHeadNode = nullptr;
        list.m_pTailNode = nullptr;
    }

    //指定范围内删除
private:
    void setSize(const unsigned size)                                      //设置大小
    {
        m_uSize = size;
    }

private:
    unsigned m_uSize;       //链表大小
    LinkNode *m_pHeadNode;  //头结点
    LinkNode *m_pTailNode;  //尾结点
};

3.栈模板,队列模板(单向链表存储)

 //Stack.h
#pragma once

template 
class CStack
{
private:
    class CLinkNode     //单向链表
    {
    public:
        CLinkNode()
        {
            m_pElement = nullptr;
            m_pNextNode = nullptr;
        }

        CLinkNode(const T& element)
        {
            m_pElement = new T(element);
            m_pNextNode = nullptr;
        }

        ~CLinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T* m_pElement;              //元素
        CLinkNode *m_pNextNode;     //下一个结点
    };

public:
    CStack()
    {
        m_pStackTop = nullptr;
        setSize(0U);
    }

    CStack(const T& element)
    {
        m_pStackTop = new CLinkNode(element);
        setSize(1U);
    }

    ~CStack()
    {
        while (m_pStackTop != nullptr)
        {
            pop();
        }
    }

    void push(const T& element)                 //压栈
    {
        CLinkNode *pNode = new CLinkNode(element);
        pNode->m_pNextNode = m_pStackTop;
        m_pStackTop = pNode;
        setSize(getSize() + 1U);
    }

    void pop()                                //出栈
    {
        if (getSize() > 0)
        {
            CLinkNode *pOldNode = m_pStackTop;
            m_pStackTop = pOldNode->m_pNextNode;
            delete pOldNode;
            setSize(getSize() - 1U);
        }
    }

    T* getTop() const    //获得栈顶元素
    {
        return m_pStackTop->m_pElement;
    }

    const unsigned getSize() const  //获得栈的大小
    {
        return m_uSize;
    }

private:
    void setSize(const unsigned size)   //设置栈大小
    {
        m_uSize = size;
    }

private:
    CLinkNode *m_pStackTop;     //栈顶
    unsigned m_uSize;           //栈的大小
};

4.栈模板(动态数组存储)

 //StackForVecotr.h
#pragma once
#include "Vector.h"

template 
class CStackForVecotr
{
public:
    CStackForVecotr(unsigned capactity)  //初始化的时候需要设定大小,大小为给定值的两倍
    {
        m_pStackTop = new CVector(capactity);
    }

    CStackForVecotr(unsigned capactity, const T& element)
    {
        m_pStackTop = new CVector(capactity);
        m_pStackTop->push_back(element);
    }

    ~CStackForVecotr()
    {
        delete m_pStackTop;
    }

    void push(const T& element)                 //压栈
    {
        if (m_pStackTop->getSize() < m_pStackTop->getCapacity())
        {
            m_pStackTop->push_back(element);
        }
        else
        {
            throw 0;
        }
    }

    void pop()                                //出栈
    {
        if (getSize() > 0)
        {
            m_pStackTop->pop_back();
        }
        else
        {
            throw 1;
        }
    }

    T* getTop()    //获得栈顶元素
    {
        int address =m_pStackTop->getSize() - 1U;
        int *ad2 = (int *)m_pStackTop;
        int *ad3 = (int *)*ad2 + address;
        return ad3;
    }

    const unsigned getSize() const  //获得栈的大小
    {
        return m_pStackTop->getSize();
    }


private:
    CVector *m_pStackTop;       //栈顶
};
 //test.cpp
//#include "LinkList.h"
//#include "Vector.h"
//#include "Stack.h"
//#include "Queue.h"
#include "StackForVecotr.h"

#include 
using namespace std;

/*动态数组
int main()
{

    CVector vec;

    for (int i = 0; i < 5000000; i++)
    {
        vec.push_back(rand());
    }

    for (CVector::Iterator it = vec.front(); it != vec.back(); it++)
    {
        cout << *it << endl;
    }

    system("pause");
    return 0;
}
*/

/*链表
int main()
{
    CLinkList list;

    for (int i = 1; i <= 500000; i++)
    {
     list.push_back(i * 2);
    }

    for (CLinkList::Iterator it = list.front(); it != list.back(); it++)
    {
        cout << *it << endl;
    }

    system("pause");
    return 0;
}
*/


/*栈
int main()
{
    {
        CStack stack(1);

        for (int i = 0; i < 50; i++)
        {
            cout << *stack.getTop() << endl;
            stack.push(rand());
        }
    }
    system("pause");
    return 0;
}
*/

/*队列
int main()
{

    {

        CQueue queue(1);

        for (int i = 0; i < 50; i++)
        {
            cout << "head: " << *queue.getHead()
            << " tail: " << *queue.getTail() << endl;
            queue.push(rand());
        }

    }

    system("pause");
    return 0;
}
*/

/*栈用动态数存储*/
int main()
{
    {
        CStackForVecotr stack(2U);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.pop();
        stack.pop();
        stack.pop();
        stack.push(22);
        stack.push(33);
        stack.push(44);

        auto size = stack.getSize();

        auto *pStack = stack.getTop();
        *pStack = 55;
    }

    return 0;
}
0 条评论
发表一条评论