【C++打怪之路Lv11】-- stack、queue和优先级队列

简介: 【C++打怪之路Lv11】-- stack、queue和优先级队列

C++为什么要学习stack、queue和优先级队列


学习C++中的栈(stack)、队列(queue)和优先级队列(priority queue)对开发者来说非常重要,因为它们是常用的数据结构,在解决各种编程问题时提供了高效的方法。

以下是它们的核心作用和特点:

1. 栈(Stack):

  特点:后进先出(LIFO),即最后入栈的元素最先出栈。

  应用:适用于函数调用、表达式求值、撤销操作等场景。例如,程序在执行递归调用时会用栈来存储函数状态。

2. 队列(Queue):

  特点:先进先出(FIFO),即最先进入队列的元素最先被处理。

  应用:适用于任务调度、消息处理、广度优先搜索等需要按顺序处理数据的场景。

3. 优先级队列(Priority Queue):

  特点:元素按优先级排序,每次取出的是优先级最高的元素,而不是按插入顺序。

  应用:适用于任务管理(例如操作系统中的任务调度)、最短路径算法(如Dijkstra算法)、数据流中找出Top K元素等场景。


这些数据结构在C++中有标准库支持(如`<stack>`、`<queue>`和`<priority_queue>`),可以帮助开发者更高效地处理特定类型的问题,提高程序的可读性和性能。


stack类


stack类的介绍

stack 是 C++ 标准模板库(STL)中的一个容器适配器,用于实现后进先出(LIFO)数据结构。

基于其他序列容器(如 dequevectorlist)构建,默认使用 deque 作为底层容

stack<int, vector<int>> st;

注:

1、定义了一个名为 st 的栈(stack)

其中包含 int 类型的元素,并使用 vector<int> 作为其底层容器

2、stack 默认使用 deque 作为底层容器,但可以通过这种方式替换成其他容器

3、特点 & 好处

  • 该栈 st 仍然保持 stack 的 后进先出 特性。
  • 使用 vector 作为底层容器意味着栈的元素实际上存储在一个 vector 中,但只能通过 stack 提供的接口(如 push()pop()top() 等)访问。

这样做的优势在于,如果对底层容器的特性(如内存管理或其他特定操作)有特殊需求,可以灵活选择适合的容器

stack的基本操作

  • push()将元素压入栈顶
  • pop()移除栈顶元素
  • top():返回栈顶元素的引用只能访问栈顶元素(通过 top()),无法直接访问其他位置的元素
  • empty():判断栈是否为空
  • size():返回栈中元素的个数

stack的模拟实现

namespace sky
{
  template<class T, class Container = vector<int>>
  class Stack
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);  // 压栈插入数据
    }
 
    void pop()
    {
      _con.pop_back();    // 删除用尾删
    }
 
    const T& top()
    {
      return _con.back();   // 后进先出
    }
 
    bool empty()
    {
      return _con.empty();
    }
 
    size_t size()
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}
 
int main()
{
  sky::Stack<int,vector<int>> st;
  st.push(1);
  st.push(2);
  st.push(3);
  st.push(4);
  st.push(5);
 
  cout << st.size() << endl;
 
  while (!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
 
  return 0;
}


queue类


queue类的介绍

1、queue 是标准库容器适配器,用于实现先进先出(FIFO)队列。

它基于底层容器(如 dequelist)进行封装

2、默认使用 deque 作为存储容器,也可以指定其他符合双端操作要求的容器。

queue 适用于需要按顺序处理数据的场景,如任务调度或广度优先搜索等

queue的基本操作

  • push():向队尾添加元素
  • pop()移除队头元素
  • front():返回队头元素的引用
  • back():返回队尾元素的引用
  • empty()检查队列是否为空
  • size():返回队列中元素的数量

queue的模拟实现

namespace sky
{
  template<class T, class Container = list<int>>
  class Queue
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);
    }
 
    void pop()
    {
      _con.pop_front();
    }
 
    T& front()
    {
      return _con.front();
    }
 
    T& back()
    {
      return _con.back();
    }
 
    bool empty()
    {
      return _con.empty();
    }
 
    size_t size()
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}
 
int main()
{
  sky::Queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
 
  cout << q.back() << endl;
 
  cout << q.size() << endl;
  while (!q.empty())
  {
    cout << q.front() << " ";
    q.pop();
  } 
 
  return 0;
}


优先级队列


优先级队列的介绍

priority_queue 是标准库容器适配器,用于实现优先级队列,其元素根据优先级自动排序。默认情况下,它使用最大堆结构,使得队头元素总是优先级最高的元素

priority_queue 适用于需要动态维护最大(或最小)元素的场景,如任务调度、路径规划等

注:需要包头文件<queue>


仿函数


什么是仿函数

priority_queue的函数原型比queuestack多了一个参数,用于指定比较函数,这个参数决定了元素在priority_queue中的排序方式

比较函数(仿函数):priority_queue需要一个比较函数(通常是仿函数)来定义元素之间的优先级顺序。默认情况下,它使用std::less<T>,这意味着它将按照从小到大的顺序排列,形成一个最大堆

这是priority_queue与queue和stack最显著的区别,因为priority_queue需要根据元素的优先级来组织数据,而queue和stack仅需要遵循基本的先进先出或后进先出原则

为什么要有仿函数

  • 自定义比较逻辑:优先级队列默认情况下是一个最大堆,即最大的元素具有最高的优先级。但有时我们可能需要根据不同的标准来排序元素,比如最小堆或者基于对象的某个成员函数。通过使用仿函数,我们可以自定义比较逻辑,使得优先级队列能够按照我们期望的顺序排列元素。
  • 状态保持:仿函数可以保持状态,这意味着它们可以在调用之间保留信息,这在某些复杂的比较逻辑中非常有用。
  • 类型安全:使用仿函数可以保证类型安全,因为编译器会在编译时检查传递给仿函数的参数类型是否正确。

优先级队列的使用

成员函数

  • push()插入元素,并自动调整位置
  • pop()移除优先级最高的元素(队头)
  • top()访问优先级最高的元素
  • empty():检查队列是否为空。
  • size():返回元素的数量

排序准则

默认使用 std::less(大顶堆),可以通过自定义比较函数来实现小顶堆或其他排序

优先级队列的模拟实现

namespace sky
{
  template<class T>
  class less
  {
  public:
    bool operator()(const T& x, const T& y)
    {
      // 在构建堆时,x < y 的意思是:如果 x 比 y 小,
      // 那么 x 的优先级低于 y,所以 y 应该排在 x 前面
      return x < y;
    }
  };
 
  template<class T>
  class greater
  {
  public:
    // 当使用 greater 作为比较器时,较小的元素会排在前面,因此可以创建一个"最小优先队列"
    bool operator()(const T& x, const T& y)
    {
      return x > y;
    }
  };
 
  template<class T, class Container = vector<int>, class Compare = less<T>>
  class priority_queue
  {
  public:
    void adjust_up(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 adjust_down(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++;
        }
        // 如果父节点比选定的子节点小,则交换
        if (com(_con[parent], _con[child]))
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
 
    // 插入元素并调整堆
    void push(const T& val)
    {
       _con.push_back(val);
       adjust_up(_con.size() - 1);
    }
 
    // 删除堆顶元素并调整堆
    void pop()
    {
      if (!_con.empty())
      {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        adjust_down(0);
      }
    }
 
    const T& top() const
    {
      return _con[0];
    }
 
    bool empty() const
    {
      return _con.empty();
    }
 
    size_t size() const
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}
 
int main()
{
  sky::priority_queue<int> pq;
  pq.push(3);
  pq.push(1);
  pq.push(5);
  pq.push(4);
  pq.push(2);
 
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;
 
  return 0;
}


关于容器适配器


目录
相关文章
|
2月前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
28 4
|
2月前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
25 4
|
2月前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
21 1
|
2月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
23 1
|
2月前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
22 1
|
2月前
|
编译器 程序员 C++
【C++打怪之路Lv7】-- 模板初阶
【C++打怪之路Lv7】-- 模板初阶
18 1
|
2月前
|
存储 C语言 C++
【C++打怪之路Lv6】-- 内存管理
【C++打怪之路Lv6】-- 内存管理
41 0
【C++打怪之路Lv6】-- 内存管理
|
2月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
38 1
|
2月前
|
存储 编译器 C语言
【C++打怪之路Lv3】-- 类和对象(上)
【C++打怪之路Lv3】-- 类和对象(上)
17 0
|
2月前
|
存储 安全 编译器
【C++打怪之路Lv1】-- 入门二级
【C++打怪之路Lv1】-- 入门二级
23 0