stack_queue | priority_queue | 仿函数

简介: stack_queue | priority_queue | 仿函数

1. stack 的使用

栈不在是一个容器,而是一个容器适配器 ,

stack的模板中第二个deque暂时不知道干什么的,后面会说


说明stack是一个容器适配器,并且为了保证严格的先进后出,所以不存在迭代器


#include<iostream>
#include<stack>
using namespace std;
int main()
{
  stack<int>v;
  v.push(1);
  v.push(2);
  v.push(3);
  v.push(4);
  while (!v.empty())//后进先出的原则
  {
    cout << v.top() << " ";//4 3 2 1
    v.pop();
  }
  return 0;
}

2. stack的模拟实现

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
using namespace std;
namespace yzq
{
  //适配器模式
  template<class T, class Container = deque<T>>//给与缺省值
  //deque 作为一个双端队列,可以非常适用与大量 头插 头删 尾插 尾删 的情况
  class stack
  {
  public:
    void push(const T& x)//插入
    {
      _con.push_back(x);//尾插
    }
    void pop()//删除栈顶元素
    {
      _con.pop_back();  
    }
    const T& top()//栈顶
    {
      return _con.back();
    }
    size_t size()//大小
    {
      return _con.size();
    }
    bool empty()//判空
    {
      return _con.empty();
    }
  private:
    Container _con;//Container 是一个符合要求的容器
  };//适配器模式
  void test()
  {
    yzq::stack<int>v;
    v.push(1);
    v.push(2);
    v.push(3);
    v.push(4);
    while (!v.empty())
    {
      cout << v.top() << " ";
      v.pop();
    }
    cout << endl;
  }
}

这里假设我们不认识 deque,那么如果stack频繁使用pop尾删,将vector< T >设置成缺省值也是非常适合的

3. queue的使用

队列同样不在是一个容器,而是一个容器适配器


说明queue为了保证严格的先进先出,所以不存在迭代器


#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int main()
{
  queue<int>v;
  v.push(1);
  v.push(2);
  v.push(3);
  v.push(4);
  while (!v.empty())//符合先进先出的原则
  {
    cout << v.front() << " ";//1 2 3 4
    v.pop();
  }
  return 0;
}

4. queue的模拟实现

#pragma once
namespace yzq
{
  template<class T, class Container=deque<T>>//给与缺省值,默认使用list<T>
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_front();  //vector没有头删,强行使用erase 效率太低
    }
    const T& front()
    {
      return _con.front();
    }
    const T& back()
    {
      return _con.back();
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;//Container 是一个符合要求的容器
  };
}

这里假设我们不认识 deque,那么如果stack频繁使用pop头删,将 list< T >设置成缺省值也是非常适合的

5. deque ——双端队列

可以在头尾双端进行插入和删除的操作,且时间复杂度为O(1),与vetcor比较,头插效率高,不需要移动元素,

与list比较,空间利用比较高


而deque就是要综合两者的优点 (想法很美好)

deque并不是真正的连续的空间,而是由一段段连续的小空间拼接而成的

一段段的小数组,若满了不扩容,在开辟一块空间,通过中控(指针数组)的方式将一个个小数组管理起来

第一个buf数组,开的是中控指针数组中间的位置

头插:

尾插:


若中控满了,就要扩容,但是扩容代价低

若为vector,本来为100个int空间,需要200个空间,就需要扩容2倍

而 中控是一个指针数组,里面都是指针,可能只需要20个指针就搞定了,所以扩容代价相对于低一些


deque优缺点

优点:

1.相比于vector,扩容代价低

2. 头插 头删,尾插尾删效率高

3. 支持随机访问


缺点:

1.中间插入删除很难搞

若中间插入删除效率高,会影响随机访问的效率,牺牲中间插入删除的效率,随机访问效率就变高了

2.没有vector和list优点极致

deque你说它跟vector比随机访问,速度不如vector,跟list比任意位置插入删除,效率没list高 ,这种就搞的很难啦,哪一项都不突出,但是都会一点

栈和队列都是需要大量的头插头删,尾插尾删的,而deque在这个场景下效率很高,所以deque被当作栈和队列的默认适配容器

6. priority_queue ——优先级队列

1. priority_queue的使用


底层是一个堆,默认容器使用vector, 最后一个模板参数代表仿函数 默认使用 less 代表小于 (后面会讲)

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int main()
{
  priority_queue<int, vector<int>>v;
  //默认为大堆,数据大的优先级高
  v.push(4);
  v.push(8);
  v.push(6);
  v.push(2);
  while (!v.empty())
  {
    cout << v.top() << " "; //8 6 4 2
    v.pop();
  }
  return 0;
}

正常来说,默认建立大堆,所以数据大的优先级高


#include<iostream>
#include<queue>
#include<functional>
int main()
{
  priority_queue<int,vector<int>,greater<int>>v;//greater作为仿函数
  //设置小堆,让小的优先级高
  v.push(4);
  v.push(8);
  v.push(6);
  v.push(2);
  while (!v.empty())
  {
    cout << v.top() << " "; //2 4 6 8
    v.pop();
  }
  return 0;
}

但若加入仿函数 greater 后,则会建立小堆,所以数据小的优先级高

2. priority_queue的模拟实现

由于是自己实现的所以要加上命名空间,避免冲突

push——插入

void adjustup(int child)//向上调整算法
    {
      Compare com;
      int parent = (child - 1) / 2;
      while (child > 0)
      {
        //建大堆
        if (com(_con[parent] ,_con[child]))
        {
          swap(_con[parent], _con[child]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
void push(const T&x)
    {
      _con.push_back(x);
      adjustup(_con.size() - 1);//向上调整算法
    }

由于是堆的插入,而堆本身也是由数组的数据构成的,所以数组加入一个数据相当于在堆最后插入一个数据,在通过向上调整算法依次交换, 不懂向上调整算法的点击这里

pop ——删除

void adjustdown(int parent)//向下调整算法
    {
      Compare com;
      int child = parent * 2+1;//假设为左孩子
      while (child<_con.size())
      {
        //建大堆
        if (child+1 < _con.size()&&com(_con[child],_con[child + 1]))
          //child+1是防止右孩子不存在导致越界
        {
          child++;
        }
        if (com(_con[parent] ,_con[child]))//将两者换一种说法,使之能=能够调用<即可
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
void pop()
    {
      swap(_con[0], _con[_con.size() - 1]);//首尾交换
      _con.pop_back();//尾删
      adjustdown(0);//向下调整算法
    }

由于要删除堆顶的数据,所以交换堆尾与堆顶数据,在删除堆尾数据,默认容器为vector,所以有pop_back 尾删的功能,而此时堆顶的数据不符合当前的位置,所以需要借助向下调整算法把该数据调整到合适的位置 不懂向下调整算法的点击这里

top —— 堆顶

const T& top()
    {
      return _con[0];
    }

堆是借助数组来实现的,所以堆顶的数据就是当前的第一个数据

仿函数问题

template <class T>
  struct Less
  {
    bool operator()(const T& x, const T& y)
    {
      return x < y;
    }
  };
  template <class T>
  struct greater
  {
    bool operator()(const T& x, const T& y)
    {
      return x > y;
    }
  };

仿函数主要是借助两个类 来重载 运算符 ( ) ,

而 Less ( x<y) 用于 建立大堆 ,greater (x>y) 用于建立小堆


Less / greater 分别都是类名 ,而模板参数 Compare 需要类型

所以 都需要加上 ,即 Less< T> / greater < T >

通过该类型在向上/向下调整算法中分别建立对象,通过对象调用对应类less/greater的重载()从而达到目的

若为默认类型Less,则调用x <y ,从而建大堆


当传入greater< T >类型后,调用对象,找到对应greater类型的重载() ,调用 x >y ,从而建小堆

完整代码实现

#include<iostream>
#include<queue>
using namespace std;
namespace yzq
{
  template <class T>
  struct Less
  {
    bool operator()(const T& x, const T& y)
    {
      return x < y;
    }
  };
  template <class T>
  struct greater
  {
    bool operator()(const T& x, const T& y)
    {
      return x > y;
    }
  };
  template<class T, class Container=vector<T>,class Compare=Less<T> >
  class priority_queue//优先级队列
  {
  public:
    void adjustup(int child)//向上调整算法
    {
      Compare com;
      int parent = (child - 1) / 2;
      while (child > 0)
      {
        //建大堆
        if (com(_con[parent] ,_con[child]))
        {
          swap(_con[parent], _con[child]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void adjustdown(int parent)//向下调整算法
    {
      Compare com;
      int child = parent * 2+1;//假设为左孩子
      while (child<_con.size())
      {
        //建大堆
        if (child+1 < _con.size()&&com(_con[child],_con[child + 1]))
          //child+1是防止右孩子不存在导致越界
        {
          child++;
        }
        if (com(_con[parent] ,_con[child]))//将两者换一种说法,使之能=能够调用<即可
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T&x)
    {
      _con.push_back(x);
      adjustup(_con.size() - 1);//向上调整算法
    }
    void pop()
    {
      swap(_con[0], _con[_con.size() - 1]);//首尾交换
      _con.pop_back();//尾删
      adjustdown(0);//向下调整算法
    }
    const T& top()
    {
      return _con[0];
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;//使用vector实现
  };
}
int main()
{
  //yzq::priority_queue<int>v;
  yzq::priority_queue<int,deque<int>,greater<int>>v;
  v.push(1);
  v.push(5);
  v.push(8);
  v.push(4);
  while (!v.empty())
  {
    cout << v.top() << " ";
    v.pop();
  }
  return 0;
}
相关文章
|
存储 设计模式 算法
【C++】stack & queue
【C++】stack & queue
348 0
【C++】stack & queue
|
1月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
33 1
|
1月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
55 0
|
5月前
|
设计模式 算法 C++
satck和queue以及priority_queue
satck和queue以及priority_queue
36 1
|
6月前
|
设计模式 算法 编译器
【C++】开始使用stack 与 queue
队列的相关习题大部分是子啊BFS中使用,这里就不在说明了
47 3
|
存储 算法 C++
C++ STL priority_queue
优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
|
算法 C++ 容器
【C++】priority_queue使用和模拟实现——仿函数(下)
【C++】priority_queue使用和模拟实现——仿函数(下)
【C++】priority_queue使用和模拟实现——仿函数(下)
|
设计模式 算法 C语言
C++实践模拟(stack,queue & priority_queue,仿函数)
C++实践模拟(stack,queue & priority_queue,仿函数)
56 0
|
存储 算法 程序员
stack、queue、priority_queue的使用和简单实现【STL】
stack、queue、priority_queue的使用和简单实现【STL】
61 0
|
存储 算法 C++
『C++ - STL』之优先级队列( priority_queue )
『C++ - STL』之优先级队列( priority_queue )