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,到这里就介绍结束了,本篇文章对你由帮助的话,期待大佬们的三连,你们的支持是我最大的动力!

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

目录
相关文章
|
13天前
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言,那就需要配置必要的环境和相关的软件,才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境,您需要确保电脑上有以下两款可用的软件,文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件,源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前,请确保您有一个文本编辑器,且有足够的经验来编写一个计算机程序,然后把它保存在一个文件中,编译并执行它。 Visual Studio Code:虽然它是一个通用的文本编辑器,但它有很多插
|
23天前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
60 5
|
21天前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
25 1
|
23天前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
44 1
|
27天前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
29 1
|
25天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
20 0
|
21天前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
21 4
|
21天前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
19 4
|
21天前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
17 1
|
1月前
|
存储 编译器 C++
【C++类和对象(下)】——我与C++的不解之缘(五)
【C++类和对象(下)】——我与C++的不解之缘(五)