c++实现双端队列

在使用c++容器的时候其底层如何实现例如 vector 容器：是一个内存可以二倍扩容的向量容器，使用方便但是对内存要求严格，弊端明显 list 容器：双向循环链表 deque 容器 :双端队列

deque容器是C++标准模版库(STL,Standard Template Library)中的部分内容。deque容器类与vector类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是，deque还支持从开始端插入数据：push_front()。

实际上双端队列是一个二维数组，但是实际存储数据的部分并不是连续的，一维数组存放指针，指向二维申请出来的空间，如图

首先申请一维空间存放指向二维的指针，例如一维空间长度为int len；则在len／4的位置先申请一块二维空间，指向前的指针*_frist与指向后的指针*_last 位于二维空间的中间，前插数据则*_frist--,后插数据则*_last++;

如果前插到二维的0下标位置，若一维数组上一个位置指向的空间为空，此时会在一维上一个位置申请二维，*_frist指向二维尾部，例如上图，会在*p 0 的位置申请二维，*_frist指向新开辟的二维的尾部，实现继续前插，若上面的所有一维都申请了二维，但是下面还有一维数组还有空，则整体将数据往下挪，把一维0号下标的二维空出来，继续前插，直到所有的一维都申请了二维并且数据放满，此时需要扩容，将一维数组2倍扩大，然后将所有数据移到新的一维数组所指向的二维数组中，满足数据位置为：（新的一维数组长度/4）的位置。尾插同理只是向下插方向相反。

下面是数据结构和基本函数

#define QUE_SIZE(T) 4096 / sizeof(T)

#define DEFAULT_QUE 2

class Deque

{

public:

  Deque();     //构造函数

  ~Deque();   // 析构函数

  Deque(const Deque &src);  // 左值引用参数构造拷贝函数 防止浅拷贝

  Deque(Deque &&src);        // 右值引用参数拷贝构造函数 防止临时量对空间时间的浪费

  Deque& operator=(const Deque &src);    //  左值引用参数赋值构造函数

  Deque& operator=(Deque &&src);          //  带右值引用参数的赋值构造函数

void push_back(int val); // 尾部入队

  void pop_back();         // 尾部删除

  void push_front(int val);  //  前插

  void pop_front();            //前删

  int front();          //返回队头元素

  int back();         //  返回队尾元素

  bool empty();   //   是否对空

private:

  int **mMapper;

  int *mFirst;

  int *mLast;

  int mMapperSize;

};

具体函数封装成类

#include<iostream>

#include<stdlib.h>

#include<string.h>

using namespace std;

#define QUE_SIZE(T) 4096 / sizeof(T)

#define DEFAULT_QUE 2

class Deque

{

public:

  Deque()

  {

  mMapper=new int*[DEFAULT_QUE]();

  mMapperSize=DEFAULT_QUE;

  mMapper[DEFAULT_QUE/]=new int[QUE_SIZE(int)];

  mFirst=mMapper[DEFAULT_QUE/]+QUE_SIZE(int)/;

  mLast=mFirst+;

  }

  ~Deque()

  {

  int i=;

  for(;i<mMapperSize;i++)

  {

    delete []mMapper[i];

    mMapper[i]=nullptr;

  }

  delete []mMapper;

  mMapper=nullptr;

  }

  Deque(const Deque &src)

  {

    mMapper=new int*[src.mMapperSize]();

    int mfirst=-;

    int mlast=-;

    bool sign=;

    int i;

    for(i=;i<src.mMapperSize;i++)

    {

       if(src.mMapper[i]==nullptr)

       {

          continue;

       }

       if(src.mMapper[i]!=nullptr)

       {

         if(sign)

         {

           mfirst=i;

           sign=;

         }

      int j;

      mMapper[i]=new int[QUE_SIZE(int)];

      for(j=;j<QUE_SIZE(int);j++)

      {

        *(mMapper[i]+j)=*(src.mMapper[i]+j);

      }

      mlast=i;

     }

    }

    mFirst=mMapper[mfirst]+(src.mFirst-src.mMapper[mfirst]);

    mLast=mMapper[mlast]+(src.mLast-src.mMapper[mlast]);

    mMapperSize=src.mMapperSize;

  }

  Deque(Deque &&src)

  {

    mMapper=src.mMapper;

    mMapperSize=src.mMapperSize;

    mFirst=src.mFirst;

    mLast=src.mLast;

    src.mMapper=nullptr;

  }

  Deque& operator=(const Deque &src)

  {

    if(this==&src)

    {

      return *this;

    }

    int i=;

    for(;i<mMapperSize;i++)

    {

      delete[]mMapper[i];

    }

    delete []mMapper;

    mMapper=new int*[src.mMapperSize]();

    int mfirst=-;

    int mlast=-;

    bool sign=-;

    for(i=;i<src.mMapperSize;i++)

    {

       if(src.mMapper[i]==nullptr)

       {

          continue;

       }

       if(src.mMapper[i]!=nullptr)

       {

         if(sign)

         {

           mfirst=i;

           sign=;

         }

      int j;

      mMapper[i]=new int[QUE_SIZE(int)];

      for(j=;j<QUE_SIZE(int);j++)

      {

        *(mMapper[i]+j)=*(src.mMapper[i]+j);

      }

      mlast=i;

     }

    }

    mFirst=mMapper[mfirst]+(src.mFirst-src.mMapper[mfirst]);

    mLast=mMapper[mlast]+(src.mLast-src.mMapper[mlast]);

mMapperSize=src.mMapperSize;

    return *this;

  }

  Deque& operator=(Deque &&src)

  {

    int i=;

    for(;i<mMapperSize;i++)

    {

      delete []mMapper[i];

    }

    delete []mMapper;

    mMapper=src.mMapper;

    mMapperSize=src.mMapperSize;

    mLast=src.mLast;

    mFirst=src.mFirst;

    src.mMapper=nullptr;

    return *this;

  }

void push_back(int val) // 尾部入队

  {

     int index = -;

     for (int i = ; i < mMapperSize; ++i)

     {

         if (mMapper[i] == nullptr)

         {

            index = i;

            continue;

         }

   // 表示last已经指向行的末尾了，需要扩容

        if (mMapper[i] + QUE_SIZE(int) == mLast)

        {

  // 说明下面还有空行，直接分配新的第二维数组

        if (i != mMapperSize - )

        {

           mMapper[i+] = new int[QUE_SIZE(int)];

           mLast = mMapper[i + ];

           break;

        }

  // 说明last下面已经没有空闲行了

        if (index != -)

        {

  // 说明上面还有空闲行，整体往上挪一行，下面就有一个空闲行了

           for (int i = index; i < mMapperSize-; ++i)

           {

               mMapper[i] = mMapper[i + ];

           }

               mMapper[mMapperSize-] = new int[QUE_SIZE(int)];

               mLast = mMapper[mMapperSize - ];

               break;

        }

        else

        {

   // 说明上面没有空闲行，一维需要开始扩容了

            int **tmpMapper = new int*[* mMapperSize];

            int idx =  * mMapperSize / ;

            for (int i = ; i < mMapperSize; ++i)

            {

                tmpMapper[idx++] = mMapper[i];

            }

                   delete[]mMapper;

                        mMapper = tmpMapper;

                        mMapperSize *= ;

                        mMapper[idx] = new int[QUE_SIZE(int)];

                        mLast = mMapper[idx];

                        break;

                    }

                }

            }

            // 添加元素

            *mLast++ = val;

  }

  void pop_back()

  {

    int i;

    bool sign=;

    for(i=;i<mMapperSize;i++)

    {

      if(mMapper[i]==mLast)

      {

        mLast=mMapper[i-]+QUE_SIZE(int);

        sign=;

        break;

      }

    }

    if(sign)

    {

      mLast--;

    }

  }

  void push_front(int val)

  {

    // 遍历第一维的数组，从下往上遍历 与尾插方法一样

     int index = -;

     int i=mMapperSize-;

     for (; i>=; i--)

     {

        if (mMapper[i] == nullptr)

        {

             index = i;

             continue;

        }

       // 表示frist已经指向行首，需要扩容

       if (mMapper[i] ==mFirst)

         {

       // 说明上面还有空行，直接分配新的第二维数组

       if (i != )

       {

           mMapper[i-] = new int[QUE_SIZE(int)];

           mFirst = mMapper[i-]+QUE_SIZE(int);

             break;

       }

     // 说明frist下面已经没有空闲行了

       if (index != -)

       {

     // 说明下面还有空闲行，整体往下挪一行，上面就有一个空闲行了

       for (i = index; i >; i--)

       {

         mMapper[i] = mMapper[i-];

       }

         mMapper[] = new int[QUE_SIZE(int)];

         mFirst= mMapper[]+QUE_SIZE(int);

          break;

        }

         else

        {

         // 说明下面没有空闲行，一维需要开始扩容了

           int **tmpMapper = new int*[* mMapperSize];

           int idx =  * mMapperSize / ;

           for (int i = ; i < mMapperSize; ++i)

           {

               tmpMapper[idx+i] = mMapper[i];

           }

               delete[]mMapper;

               mMapper = tmpMapper;

               mMapperSize *= ;

               mMapper[idx-] = new int[QUE_SIZE(int)];

               mFirst = mMapper[idx-]+QUE_SIZE(int);

               break;

                    }

                }

            }

            // 添加元素

            *mFirst-- = val;

  }

  void pop_front()

  {

    int i;

    bool sign=;

    for(i=;i<mMapperSize;i++)

    {

      if(mMapper[i]+QUE_SIZE(int)==mFirst)

      {

        mFirst=mMapper[i+];

        sign=;

        break;

      }

    }

    if(sign)

    {

      mFirst++;

    }

  }

  int front()

  {

    int i;

    for(i=;i<mMapperSize;i++)

    {

      if(mMapper[i]+QUE_SIZE(int)==mFirst)

      {

        return *mMapper[i+];

      }

    }

    return *(mFirst+);

  }

  int back()

  {

    int i=;

    for(;i<mMapperSize;i++)

    {

      if(mMapper[i]==mLast)

      {

        return *(mMapper[i-]+QUE_SIZE(int));

      }

    }

    return *(mLast-);

  }

  bool empty()

  {

    return mFirst+==mLast;

  }

private:

  int **mMapper;

  int *mFirst;

  int *mLast;

  int mMapperSize;

};

int main()

{

     Deque s1;

     Deque s2;

     int i=;

     for(;i<;i++)

     {

       s1.push_back(i);

     }

     s2=s1;

     for(i=;i<;i++)

     {

      cout<<s2.front()<<' ';

       s2.pop_front();

     }

    cout<<endl;

    return ;

}

巴特西

c++实现双端队列

最新文章

热门文章