C++【STL】之stack和queue学习

简介: C++ STL stack和queue常用接口和模拟实现详细讲解,干货满满!

1. 容器适配器

1.1 适配器的概念

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

类似于以上图片中的电源转换插头,可以将用两脚插头来适配使用三角插头,它就起到了适配器的用。

1.2 STL标准库中stack和queue的底层结构

虽然stackqueue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stackqueue只是对其他容器的接口进行了包装,STLstackqueue默认使用deque,比如:

2. 栈stack

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

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

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

  • empty:判空操作
  • back:获取尾部元素操作
  • push_back:尾部插入元素操作
  • pop_back:尾部删除元素操作
  1. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

2.1 stack的使用

栈有两个模板参数,第一个参数T表示栈中保存的元素类型,也就是底层容器的元素类型;第二个参数Container表示实现栈时所使用的底层容器,这里缺省为双端队列deque

int main()
{
   
   
    //设置底层容器
    stack<int> s1;    //默认为deque
    stack<int, vector<int>> s2;    //指定为vector
    stack<char, list<char>> s3;    //指定为list

    //查看类型
    cout << typeid(s1).name() << endl;    
    cout << typeid(s2).name() << endl;
    cout << typeid(s3).name() << endl;

    return 0;
}

下面我们来讲解一下stack常用接口的使用,有兴趣的大佬们可以前往官方文档(点击跳转)进一步了解

  • empty()接口:判空
  • size()接口:查看大小
  • top()接口:查看栈顶元素
  • push()接口:入栈
  • pop()接口:出栈
int main()
{
   
   
    stack<int> s;    //构造栈对象

    cout << "empty(): " << s.empty() << endl; 
    cout << "size(): " << s.size() << endl;
    cout << "-------------------" << endl;

    s.push(4);     //入栈操作
    s.push(1);
    s.push(2);
    cout << "empty(): " << s.empty() << endl; //判空
    cout << "size(): " << s.size() << endl; //查看大小
    cout << "top(): " << s.top() << endl; //查看栈顶元素
    cout << "-------------------" << endl;

    s.pop(); //出栈操作
    s.pop();
    cout << "empty(): " << s.empty() << endl;
    cout << "size(): " << s.size() << endl;
    cout << "top(): " << s.top() << endl;
    cout << "-------------------" << endl;

    return 0;
}

2.2 stack模拟实现

容器适配器在模拟实现时,需要借助其他容器的接口复用,这里以使用 vector为例

namespace Sakura
{
   
   
    //模板参数2底层容器的缺省值设为vector
    template<class T, class Container = vector<int>>
    class stack
    {
   
   
    public:
        //默认构造函数不接受传参,需要提供一个带缺省参数的构造函数
        stack(const Container& c = Container())
            :_c(c)
        {
   
   }

        bool empty() const
        {
   
   
            return _c.empty();
        }

        size_t size() const
        {
   
   
            return _c.size();
        }

        T& top()
        {
   
   
            return _c.back();
        }

        const T& top() const
        {
   
   
            return _c.back();
        }

        void push(const T& val)
        {
   
   
            _c.push_back(val);
        }

        void pop()
        {
   
   
            _c.pop_back();
        }

    private:
        Container _c;
    };
}

3. 队列queue

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

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

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

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_front:在队列头部出队列
  1. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

3.1 queue的使用

队列有两个模板参数,第一个参数T表示队列中保存的元素类型,也就是底层容器的元素类型;第二个参数Container表示实现队列时所使用的底层容器,这里缺省为双端队列deque

int main()
{
   
   
    //设置底层容器
    queue<int> q1;    //默认使用deque
    queue<double, vector<double>> q2;    //指定为vector
    queue<char, list<char>> q3;    //指定为list

    //查看类型
    cout << typeid(q1).name() << endl;    
    cout << typeid(q2).name() << endl;
    cout << typeid(q3).name() << endl;

    return 0;
}

下面我们来讲解一下queue常用接口的使用,有兴趣的大佬们可以前往官方文档(点击跳转)进一步了解

  • empty()接口:判空
  • size():查看大小
  • front():查看对头元素
  • back():查看队尾元素
  • push():入队
  • pop():出队
int main()
{
   
   
    queue<int> q;    //构造出队列对象

    cout << "empty(): " << q.empty() << endl;
    cout << "size(): " << q.size() << endl;
    cout << "-------------------" << endl;

    q.push(1); //入队操作
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    q.push(6);
    cout << "empty(): " << q.empty() << endl; //判空
    cout << "size(): " << q.size() << endl;   //查看大小
    cout << "front(): " << q.front() << endl; //查看队头元素
    cout << "back(): " << q.back() << endl;   //查看队尾元素
    cout << "-------------------" << endl;

    q.pop(); //出队操作
    q.pop();
    q.pop();
    cout << "empty(): " << q.empty() << endl;
    cout << "size(): " << q.size() << endl;
    cout << "front(): " << q.front() << endl;
    cout << "back(): " << q.back() << endl;
    cout << "-------------------" << endl;

    return 0;
}

3.2 queue模拟实现

这里借用list作为底层容器来实现队列

#pragma once
#include <iostream>
#include <list>
using namespace std;

namespace Sakura
{
   
   
    //模板参数2底层容器的缺省值设为list
    template<class T, class Container = list<T>>
    class queue
    {
   
   
    public:
        queue(const Container& c = Container())
            :_c(c)
        {
   
   }

        bool empty() const
        {
   
   
            return _c.empty();
        }

        size_t size() const
        {
   
   
            return _c.size();
        }

        T& front()
        {
   
   
            return _c.front();
        }
        const T& front() const
        {
   
   
            return _c.front();
        }

        T& back()
        {
   
   
            return _c.back();
        }
        const T& back() const
        {
   
   
            return _c.back();
        }

        void push(const T& val)
        {
   
   
            _c.push_back(val);
        }

        void pop()
        {
   
   
            _c.pop_front();
        }

    private:
        Container _c;
    };
}

C++【STL】之stack和queue,到这里就介绍结束了,本篇文章对你由帮助的话,期待大佬们的三连,你们的支持是我最大的动力!

文章有写的不足或是错误的地方,欢迎评论或私信指出,我会在第一时间改正!

目录
相关文章
|
14天前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
6天前
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
33 1
|
17天前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
2月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
61 21
|
14天前
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
14天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
17天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
14天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
14天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
2月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
73 19