AI 助理
文档备案控制台
开发者社区 云原生 文章 正文

c++的学习之路：17、stack、queue与priority_queue

2024-04-22 199
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： c++的学习之路：17、stack、queue与priority_queue

一、stack的介绍和使用

1、stack的介绍

和之前一样这里也是直接介绍一下文档，使用方式和之前的模板大差不差，如下方截图就是cplusplus的介绍，下面四点就是文档上面的翻译，其他的就不详细说了，数据结构里面有更加详细的介绍。

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2、stack的使用

下面的一个表格就是常用的几个函数与接口说明，就不一一说明怎么使用了，和之前vector、list、string所演示的都差不多。

函数说明 接口说明
stack() 构造空的栈
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出

3、stack的模拟实现

这里是直接利用vector作为一个缺省值，直接用模板去创建一栈，这样都可以直接复用vector的函数，这样实现起来就十分容易加上轻松了，如下方代码所示，因为栈不支持迭代器，不能遍历只能一次出一个结果如下方图片所示，其实这里是我康吃康吃写了一个类似c写的那种，然后看了一下源码，大佬不愧是大佬，好轻松。

namespace ly1
{
  template<class T, class Container = vector<T>>
  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;
  };
 
  void Test_Stack()
  {
    stack<int> s1;
    s1.push(1);
    s1.push(2);
    s1.push(3);
    s1.push(4);
    while (!s1.empty())
    {
      cout << s1.top() << ' ';
      s1.pop();
    }
    cout << endl;
  }
}

二、queue的介绍和使用

1、queue的介绍

和之前一样这里也是直接介绍一下文档，使用方式和之前的模板大差不差，如下方截图就是cplusplus的介绍，下面四点就是文档上面的翻译，其他的就不详细说了，数据结构里面有更加详细的介绍。

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2、queue的使用

下面的一个表格就是常用的几个函数与接口说明，就不一一说明怎么使用了，和之前vector、list、string所演示的都差不多。

函数声明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空，是返回true，否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列

3、queue的模拟实现

这里也是利用复用直接写的代码和测试如下。

namespace ly2
{
  template<class T, class Container = list<T>>
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
 
    void pop()
    {
      _con.pop_front();
    }
 
    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;
  };
 
  void Test_Queue()
  {
    queue<int> q1;
    q1.push(1);
    q1.push(2);
    q1.push(3);
    q1.push(4);
    while (!q1.empty())
    {
      cout << q1.front() << " ";
      q1.pop();
    }
    cout << endl;
  }
}

三、priority_queue的介绍和使用

1、priority_queue的介绍

下面就是优先队列的文档介绍。

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空size()：返回容器中有效元素个数

front()：返回容器中第一个元素的引用

push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2、priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明 接口说明
priority_queue()/priority_queue(first,
last)		 构造一个空的优先级队列
empty( ) 检测优先级队列是否为空，是返回true，否则返回
false
top( ) 返回优先级队列中最大(最小元素)，即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素，即堆顶元素

3、priority_queue的模拟实现

这个原理有点像我之前写数据结构的堆，实现方法也差不多，这个优先队列可以进行排序，他默认是降序，代码实现与测试如下。

namespace ly3
{
  template<class T>
  struct less
  {
    bool operator()(const T& left, const T& right)
    {
      return left < right;
    }
  };
 
  template<class T>
  struct greater
  {
    bool operator()(const T& left, const T& right)
    {
      return left > right;
    }
  };
 
  template<class T, class Container = std::vector<T>, class Compare = less<T>>
  class priority_queue
  {
  public:
    priority_queue() : c() {}
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
      : c(first, last)
    {
      int count = c.size();
      int root = ((count - 2) >> 1);
      for (; root >= 0; root--)
        AdjustDown(root);
    }
 
    void push(const T& data)
    {
      c.push_back(data);
      AdjustUP(c.size() - 1);
    }
 
    void pop()
    {
      if (empty())
        return;
 
      swap(c.front(), c.back());
      c.pop_back();
      AdjustDown(0);
    }
 
    size_t size()const
    {
      return c.size();
    }
 
    bool empty()const
    {
      return c.empty();
    }
 
    const T& top()const
    {
      return c.front();
    }
  private:
    void AdjustUP(int child)
    {
      int parent = ((child - 1) >> 1);
      while (child)
      {
        if (Compare()(c[parent], c[child]))
        {
          swap(c[child], c[parent]);
          child = parent;
          parent = ((child - 1) >> 1);
        }
        else
        {
          return;
        }
      }
    }
 
    void AdjustDown(int parent)
    {
      size_t child = parent * 2 + 1;
      while (child < c.size())
      {
        if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
          child += 1;
        if (Compare()(c[parent], c[child]))
        {
          swap(c[child], c[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
          return;
      }
    }
  private:
    Container c;
  };
 
  void Test_Priority_Queue()
  {
    ly3::priority_queue<int> q1;
    q1.push(5);
    q1.push(1);
    q1.push(4);
    q1.push(2);
    q1.push(3);
    q1.push(6);
    while (!q1.empty())
    {
      cout << q1.top() << " ";
      q1.pop();
    }
    cout << endl;
  }
}

四、代码

1、stack

#pragma once
 
namespace ly1
{
  template<class T, class Container = vector<T>>
  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;
  };
 
  void Test_Stack()
  {
    stack<int> s1;
    s1.push(1);
    s1.push(2);
    s1.push(3);
    s1.push(4);
    while (!s1.empty())
    {
      cout << s1.top() << ' ';
      s1.pop();
    }
    cout << endl;
  }
}


2、queue

#pragma once
 
namespace ly2
{
  template<class T, class Container = list<T>>
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
 
    void pop()
    {
      _con.pop_front();
    }
 
    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;
  };
 
  void Test_Queue()
  {
    queue<int> q1;
    q1.push(1);
    q1.push(2);
    q1.push(3);
    q1.push(4);
    while (!q1.empty())
    {
      cout << q1.front() << " ";
      q1.pop();
    }
    cout << endl;
  }
}

3、priority_queue

#pragma once
 
namespace ly3
{
  template<class T>
  struct less
  {
    bool operator()(const T& left, const T& right)
    {
      return left < right;
    }
  };
 
  template<class T>
  struct greater
  {
    bool operator()(const T& left, const T& right)
    {
      return left > right;
    }
  };
 
  template<class T, class Container = std::vector<T>, class Compare = less<T>>
  class priority_queue
  {
  public:
    priority_queue() : c() {}
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
      : c(first, last)
    {
      int count = c.size();
      int root = ((count - 2) >> 1);
      for (; root >= 0; root--)
        AdjustDown(root);
    }
 
    void push(const T& data)
    {
      c.push_back(data);
      AdjustUP(c.size() - 1);
    }
 
    void pop()
    {
      if (empty())
        return;
 
      swap(c.front(), c.back());
      c.pop_back();
      AdjustDown(0);
    }
 
    size_t size()const
    {
      return c.size();
    }
 
    bool empty()const
    {
      return c.empty();
    }
 
    const T& top()const
    {
      return c.front();
    }
  private:
    void AdjustUP(int child)
    {
      int parent = ((child - 1) >> 1);
      while (child)
      {
        if (Compare()(c[parent], c[child]))
        {
          swap(c[child], c[parent]);
          child = parent;
          parent = ((child - 1) >> 1);
        }
        else
        {
          return;
        }
      }
    }
 
    void AdjustDown(int parent)
    {
      size_t child = parent * 2 + 1;
      while (child < c.size())
      {
        if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
          child += 1;
        if (Compare()(c[parent], c[child]))
        {
          swap(c[child], c[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
          return;
      }
    }
  private:
    Container c;
  };
 
  void Test_Priority_Queue()
  {
    ly3::priority_queue<int> q1;
    q1.push(5);
    q1.push(1);
    q1.push(4);
    q1.push(2);
    q1.push(3);
    q1.push(6);
    while (!q1.empty())
    {
      cout << q1.top() << " ";
      q1.pop();
    }
    cout << endl;
  }
}

五、思维导图



文章标签：
容器
C++
算法
存储
关键词：
C++ priority_queue
C++ stack queue
C++ queue
C++ stack
C++学习
懒懒学c
目录
相关文章
羑悻的小杀马特
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
羑悻的小杀马特
292 12
ephemerals__
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
434 21
ephemerals__
|
存储 算法 C++
【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`（优先级队列）。`priority_queue`根据严格的弱排序标准设计，确保其第一个元素始终是最大元素。它底层使用堆结构实现，支持大堆和小堆，默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`，通过仿函数控制堆的类型，并调用封装容器的接口实现功能。最后，感谢大家的支持与关注。
ephemerals__
952 1
是乙太呀
|
算法 网络安全 区块链
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法（如DES、3DES、AES和国密SM4）及其应用场景，包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法，并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程，以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
是乙太呀
419 4
2023/11/10学习记录-C/C++对称分组加密DES
蓝易云
|
C++ 开发者
C++学习之继承
通过继承，C++可以实现代码重用、扩展类的功能并支持多态性。理解继承的类型、重写与重载、多重继承及其相关问题，对于掌握C++面向对象编程至关重要。希望本文能为您的C++学习和开发提供实用的指导。
蓝易云
246 16
梦笔生花伟
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言，那就需要配置必要的环境和相关的软件，才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境，您需要确保电脑上有以下两款可用的软件，文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件，源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前，请确保您有一个文本编辑器，且有足够的经验来编写一个计算机程序，然后把它保存在一个文件中，编译并执行它。 Visual Studio Code：虽然它是一个通用的文本编辑器，但它有很多插
梦笔生花伟
640 6
平凡程序猿~
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
425 0
ephemerals__
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
539 12
hahaha无
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
280 0
hahaha无
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
452 0