【CPP】栈、双端队列、队列、优先级队列与反向迭代器-阿里云开发者社区

关于我：

睡觉待开机：个人主页个人专栏: 《优选算法》《C语言》《CPP》生活的理想，就是为了理想的生活!作者留言

PDF版免费提供：倘若有需要，想拿我写的博客进行学习和交流，可以私信我将免费提供PDF版。

留下你的建议：倘若你发现本文中的内容和配图有任何错误或改进建议，请直接评论或者私信。

倡导提问与交流：关于本文任何不明之处，请及时评论和私信，看到即回复。

1.前言

栈与队列，是我们平常经常用到的数据结构之一，尤其做题的时候会经常用到。那栈是怎么实现的？为什么这么实现？本文将简单回答并整理。

2.栈

2.1栈的简介

栈是一种 特殊的线性表，具有数据 先进后出 特点。

CPP库参考文档：stl_stack

栈提供了常见的几个接口：push\pop\top\size\empty

2.2栈接口的认识

construct

//可以构造一个空的stack
stack<int> s;
//可以先构造一个deque，再将其值赋值给sv进行构造
deque<int> v(6, 6);
stack<int> sv(v);
while (!sv.empty())
{
  cout << sv.top() << " ";
  sv.pop();
}//6 6 6 6 6 6
cout << endl;

swap

stack<int> s1;//空的栈
deque<int> v(6, 6);
stack<int> s2(v);//有内容的栈
s2.swap(s1);
cout << "this is s1" << ":" << endl;
while (!s1.empty())
{
  cout << s1.top() << " ";
  s1.pop();
}
cout << endl;
cout << "this is s2" << ":" << endl;
while (!s2.empty())
{
  cout << s2.top() << " ";
  s2.pop();
}
cout << endl;
/*this is s1:
6 6 6 6 6 6
this is s2:*/

栈中的迭代器在哪？

栈作为一种容器，是没有迭代器的。之所以不提供迭代器，因为迭代器具有随机访问的功能，这会打破栈先进后出的特性。

2.3栈的简化模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;
namespace szg
{
    template<class T, class Container = vector<T>>
    class stack
    {
    private:
        Container _st;
    public:
        void push_back(const T& num)
        {
            _st.push_back(num);
        }
        void pop_back()
        {
            _st.pop_back();
        }
        bool empty()
        {
            return _st.empty();
        }
        size_t size()
        {
            return _st.size();
        }
        const T& top()
        {
            return _st.back();
        }
    };
}

2.4适配器模式

适配器模式是指软件开发中的一种经典设计模式，适配器模式是一种将一个类的接口转换成客户希望的另外一个接口的设计模式。由于其转变方便，而受到软件设计者们的喜爱，在上文模拟stack的过程中，template<class T, class Container = vector<T>>的container就充当了适配器的角色。

实际开发：

在实际开发过程中，我们经常遇到这样的事情，我们根据初步的需求制定了一个基类，在开发过程中才了解到详细的需求或者需求发生了变动。而开发工作中的接口早已经定义完毕，并已经大规模投入编码。此时若改动接口的定义会造成很多编码上重复性的修改工作，并进而有可能造成修改不完全而导致的语义错误或逻辑错误。语义错误尚可以在编译阶段发现，而一旦发生逻辑性的错误，后果将会非常严重，甚至足以导致系统崩溃。此时就需要用到适配器模式的设计方法。

主要应用：

适配器模式主要应用于，当接口里定义的方法无法满足客户的需求，或者说接口里定义的方法的名称或者方法界面与客户需求有冲突的情况。

两类模式：

对象适配器模式 - 在这种适配器模式中，适配器容纳一个它我包裹的类的实例。在这种情况下，适配器调用被包裹对象的物理实体。
类适配器模式 - 这种适配器模式下，适配器继承自已实现的类（一般多重继承）。

既然说到适配器这个话题，我们简单来介绍一下STL库中最常用的适配器——deque

3.deque双端队列

deque虽然叫做双端队列，但实在是跟队列没什么关系，甚至说底层完全不是队列。deque是STL中的容器之一，是经典的适配器容器，他被创作出来最重要的应用场景就是做类适配器而存在。

deque是一种“全面发展”容器选手，融合了vector和list的特性。

3.1deque的特性

之所以说deque是一种融合vector和list的特性，是因为deque的特性：

除此之外，他不但支持vector的[]随机访问，还支持list的头插头删效率很高的特点。

可谓是“能文能武”，这么“全能”的deque底层结构是如何的呢？

3.2deque的内部构造

deque的内部控制是依靠迭代器实现的。

● cur是指向当前的访问元素

● first是指向当前buff的开始元素

● end是指向当前buff的末尾元素的下一个地址

● node是指向当前buff在中控数组中存放的位置

3.3deque的操作逻辑

deque的插入和删除，效率很高：

deque的头插尾插效率是挺高的。这是因为尾插一个元素后，迭代器会看看中控数组最后一个buff是否还有空间，如果有则尾插到最后一个buff，如果没有就新开一个buff插入。头插一个元素，他会现在中控数组的头部开一个buff，因为默认是从中控数组中间开始新增的，所以可以支持常数时间开空间，之后同尾插同理。

中间插入插入元素处理比较麻烦

deque中间插入有两种设计，

如果中间插入元素后面所有元素都往后挪动一位，效率比较低
如果中间插入元素改变buff的大小，那么上面[]访问规则就不适用，会很麻烦。
deque的元素[]访问计算规则，且[]访问效率一般
一般情况下，buff每个都是相同大小并且没有头插新元素时候，下标访问可以采用
● 先找是第几个buff，n/buff.size()
● 在确定是这个buff中的第几个元素，n%buff.size()
但是如果有头插元素，首先应该减去第一个buff元素的个数，然后在进行上面步骤。
● n-=buff1.size()

void test_op1()
{
  srand(time(0));
  const int N = 1000000;
  deque<int> dq;
  vector<int> v;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand() + i;
    v.push_back(e);
    dq.push_back(e);
  }
  int begin1 = clock();
  sort(v.begin(), v.end());
  int end1 = clock();
  int begin2 = clock();
  sort(dq.begin(), dq.end());
  int end2 = clock();
  printf("vector:%d\n", end1 - begin1);
  printf("deque:%d\n", end2 - begin2);
}
//vector:259
//deque:1263
void test_op2()
{
  srand(time(0));
  const int N = 1000000;
  deque<int> dq1;
  deque<int> dq2;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand() + i;
    dq1.push_back(e);
    dq2.push_back(e);
  }
  int begin1 = clock();
  sort(dq1.begin(), dq1.end());
  int end1 = clock();
  int begin2 = clock();
  // 拷贝到vector
  vector<int> v(dq2.begin(), dq2.end());
  sort(v.begin(), v.end());
  dq2.assign(v.begin(), v.end());
  int end2 = clock();
  printf("deque sort:%d\n", end1 - begin1);
  printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
//deque sort : 1345
//deque copy vector sort, copy back deque : 358

经过上面分析之后，也许你就会发现deque是挺“全能”的，也挺“全不能”的：

在方括号随机访问上，他比不上vector方括号访问的极致效率
在中间插入删除元素时候，又比不上list中间插入删除的极致效率

3.4deque作为stack/queue适配器的优先性？

为什么CPP库中选择deque作为stack/queue的适配器呢？

因为stack和queue都只会用到头插尾插头删尾删，恰好deque头尾插删效率都很好。也可以说，deque就是专门为stack/queue适配专门设计的一个容器。

4.队列queue

queue 是队列的含义，其特点是保证了数据先进先出，后进后出的特点，底层可以用vector、list或deque进行适配。

4.1队列的重要接口

与栈不同，队列提供了下面几个接口：

这里不再过多赘述。

4.2队列的简单模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<deque>
namespace szg
{
  template<class T, class Container = std::deque<T>>
  class queue
  {
  private:
    Container _con;
  public:
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
    T& front()
    {
      return _con.front();
    }
    T& back()
    {
      return _con.back();
    }
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_front();
    }
  };
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
#include<iostream>
int main()
{
  szg::queue<int> q;
  for (int i = 0; i < 100; i++)
  {
    q.push(i);
  }
  while (!q.empty())
  {
    std::cout << q.front() << " ";
    q.pop();
  }
  std::cout << std::endl;
  //0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
  return 0;
}

4.3队列与栈的异同

队列与栈的差异重点在于相同序列进入容器，出数据会有所不同。

5.priority_queue优先级队列 -> 堆

5.1简单介绍

优先级队列不是队列，是一种容器适配器，底层是大堆。

在优先级队列提供了一些接口允许公开调用：

5.2简单使用

// 优先级队列，默认底层是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);
while (!ps.empty())
{
  cout << ps.top() << " ";
  ps.pop();
}//4 3 2 1

那可以让他变成小堆吗？当然可以。

// 优先级队列，可以用仿函数置为小堆
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(1);
while (!pq.empty())
{
  cout << pq.top() << " ";
  pq.pop();
}//1 2 3 4

// 我们发现sort默认排序为升序。
vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{
  cout << *it << " ";
  it++;
}//1 3 4 2
cout << endl;
sort(v.begin(), v.end());
it = v.begin();
while (it != v.end())
{
  cout << *it << " ";
  it++;
}//1 2 3 4

为了让sort变成升序，我们也可以用仿函数进行设置。

vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{
  cout << *it << " ";
  it++;
}//1 3 4 2
cout << endl;
sort(v.begin(), v.end(), greater<int>());
it = v.begin();
while (it != v.end())
{
  cout << *it << " ";
  it++;
}//4 3 2 1

这里需要重点区分的是：

priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());

我们发现两个greater一个带括号一个不带，这是什么情况呢？

模板参数与函数参数的需要

要注意优先级队列是一种模板，需要的是类型进行实例化，而sort是模板实例化出来的一种函数，需要迭代器区间和具体的比较仿函数对象，而不是仅仅一个仿函数类型就行。

既然上面用到了仿函数，下面进行简单介绍。

5.3仿函数

仿函数：也称函数对象，仿函数是一种特殊的对象！他的对象可以像函数一样去使用。

下面进行举例：

//仿函数类
struct Less
{
public:
  bool operator()(const int& x, const int& y)
  {
    return x < y;
  }
};
void Test()
{
  Less lessfunc;
  cout << lessfunc(5,6) << endl; // 结果：1

这里需要注意哈，上面的数字5和6作为参数传递给operator()，如果要用引用来接收，必须前面加上const，因为这是引用常量值。

//仿函数类
struct Less
{
public:
  bool operator()(const int& x, const int& y)
  {
    return x < y;
  }
};
void Test()
{
  Less lessfunc;
  cout << lessfunc(5,6) << endl;//1
  vector<int> v = { 1,3,4,2 };
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    it++;
  }//1 3 4 2
  cout << endl;
  sort(v.begin(), v.end(), lessfunc);
  it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    it++;
  }//1 2 3 4
}

然后上面的仿函数类可以加上模板的语法，们用的 greater<int> 差不多了。

//仿函数类
template<typename T>
struct Less
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
void Test()
{
  vector<int> v = { 1,3,4,2 };
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  sort(v.begin(), v.end(), Less<int>());
  it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    it++;
  }
}

5.4优先级队列模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;
template<typename T>
struct Less
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
template<typename T>
struct Greater
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
};
template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:
  Container _con;
public:
  void adjust_up(int child)
  {
    Compare com;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
      if (com(_con[child], _con[parent]))
      {
        swap(_con[child], _con[parent]);
        child = parent;
        parent = (child - 1) / 2;
      }
      else
      {
        break;
      }
    }
  }
  void push(const T& x)
  {
    _con.push_back(x);
    adjust_up(_con.size() - 1);
  }
  void adjust_down(int parent)
  {
    Compare com;
    int child = parent * 2 + 1;
    while (child < _con.size())
    {
      if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
      {
        child = child + 1;
      }
      if (com(_con[child], _con[parent]))
      {
        swap(_con[child], _con[parent]);
        parent = child;
        child = parent * 2 + 1;
      }
      else
      {
        break;
      }
    }
  }
  void pop()
  {
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    adjust_down(0);
  }
  size_t size()
  {
    return _con.size();
  }
  bool empty()
  {
    return _con.empty();
  }
  const T& top()
  {
    return _con[0];
  }
};

//指针模板
template<class T>
struct GreaterPDate
{
  bool operator()(const T& d1, const T& d2)
  {
    return *d1 > *d2;
  }
};
void test_priority_queue2()
{
  priority_queue<Date*, vector<Date*>, GreaterPDate<Date*>> pqptr;
  Date d1(2024, 4, 14);
  Date d2(2024, 4, 11);
  Date d3(2024, 5, 15);
  pqptr.push(&d1);
  pqptr.push(&d2);
  pqptr.push(&d3);
  while (!pqptr.empty())
  {
    cout << *(pqptr.top()) << " ";
    pqptr.pop();
  }
  cout << endl;
}

6.反向迭代器

6.1简单介绍

下面我用库函数来进行一个简单演示。

std::list<int> l = { 1,2,3,4,5,6 };
std::list<int>::reverse_iterator rit = l.rbegin();
while (rit != l.rend())
{
  std::cout << *rit << " ";
  ++rit;
}//6 5 4 3 2 1
std::cout << std::endl;

6.2反向迭代器的设计思路

思路1：我们可以像前面实现const迭代器一样写一个类，显然，这样我们即使写模板也需要针对不同的容器进行写不同的反向迭代器。
思路2：封装iterator，然后重载其部分运算符。
下面来重点介绍第二种思路的实现方式：

这样的好处是，我们只需要设计一个反向迭代器类，就可以根据不同的正向迭代器自由变换其反向迭代器。

6.3反向迭代器的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
namespace szg
{
  template<class Tterator, class Ref, class Ptr>
  class ReverseIterator
  {
  private:
    Tterator _it;
  public:
    typedef ReverseIterator<Tterator, Ref, Ptr> Self;
    //构造函数
    ReverseIterator(Tterator it)
      :_it(it)
    {}
    //解引用
    Ref operator*()
    {
      Tterator temp = _it;
      temp--;
      return *temp;
    }
    //->函数
    Ptr operator->()
    {
      return &(this->operator*());
    }
    //前置++
    Self& operator++()
    {
      --_it;
      return *this;
    }
    
    //前置--
    Self& operator--()
    {
      ++_it;
      return *this;
    }
    //!=函数重载
    bool operator!=(const Self& s)
    {
      return _it != s._it;
    }
  };
}

#include"List.h"
#include<list>
void test()
{
  szg::list<int> l = { 1, 2, 3, 4, 5, 6 };
  /*l.push_back(1);
  l.push_back(2);
  l.push_back(3);
  l.push_back(4);
  l.push_back(5);
  l.push_back(6);*/
  szg::list<int>::reverse_iterator rit = l.rbegin();
  while (rit != l.rend())
  {
    std::cout << *rit << " ";
    ++rit;
  }//6 5 4 3 2 1
  std::cout << std::endl;
}
int main()
{
  //std::list<int> l = { 1,2,3,4,5,6 };
  //std::list<int>::reverse_iterator rit = l.rbegin();
  //while (rit != l.rend())
  //{
  //  std::cout << *rit << " ";
  //  ++rit;
  //}//6 5 4 3 2 1
  //std::cout << std::endl;
  test();
  return 0;
}

6.4rbegin、rend的解释

在库中，使用的是第一种方式设计的rbegin和rend，为什么呢？没啥意义，感觉单纯与begin，end对称一些。在解引用的时候，一直是解引用的下一个值而已。

好的，如果本篇文章对你有帮助，不妨点个赞~谢谢。

EOF

【CPP】栈、双端队列、队列、优先级队列与反向迭代器

1.前言

2.栈

2.1栈的简介

2.2栈接口的认识

construct

swap

栈中的迭代器在哪？

2.3栈的简化模拟实现

2.4适配器模式

3.deque双端队列

3.1deque的特性

3.2deque的内部构造

3.3deque的操作逻辑

3.4deque作为stack/queue适配器的优先性？

4.队列queue

4.1队列的重要接口

4.2队列的简单模拟实现

4.3队列与栈的异同

5.priority_queue优先级队列 -> 堆

5.1简单介绍

5.2简单使用

5.3仿函数

5.4优先级队列模拟实现

6.反向迭代器

6.1简单介绍

6.2反向迭代器的设计思路

6.3反向迭代器的模拟实现

6.4rbegin、rend的解释

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【CPP】栈、双端队列、队列、优先级队列与反向迭代器

1.前言

2.栈

2.1栈的简介

2.2栈接口的认识

construct

swap

栈中的迭代器在哪？

2.3栈的简化模拟实现

2.4适配器模式

3.deque双端队列

3.1deque的特性

3.2deque的内部构造

3.3deque的操作逻辑

3.4deque作为stack/queue适配器的优先性？

4.队列queue

4.1队列的重要接口

4.2队列的简单模拟实现

4.3队列与栈的异同

5.priority_queue优先级队列 -> 堆

5.1简单介绍

5.2简单使用

5.3仿函数

5.4优先级队列模拟实现

6.反向迭代器

6.1简单介绍

6.2反向迭代器的设计思路

6.3反向迭代器的模拟实现

6.4rbegin、rend的解释

热门文章

最新文章

相关课程

相关电子书