【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)

简介: 在C++中​​std::stack​​​是一个模板类,它是基于容器的适配器,用于实现堆栈数据结构。堆栈是一种后进先出(LIFO)的数据结构,类似于现实生活中的一叠盘子。

@​​TOC​
前言
文章绑定了VS平台下std::stack和std::queue的源码,大家可以下载了解一下😍前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,以及学习了几个STL的结构也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关C++比较重要的知识点—— stack & queue(STL)。下面话不多说坐稳扶好咱们要开车了😍
stack

  1. stack概念
    ​​stack 的文档介绍​​
    在C++中​​std::stack​​​是一个模板类,它是基于容器的适配器,用于实现堆栈数据结构。堆栈是一种后进先出(LIFO)的数据结构,类似于现实生活中的一叠盘子。​​std::stack​​​类位于​​​​头文件中,并且是C++标准库的一部分。它提供了一组成员函数和操作符,用于对堆栈进行操作。
  2. stack特点
  3. 后进先出(LIFO):​​std::stack​​是一种后进先出的数据结构,这意味着最后压入堆栈的元素将首先被弹出。
  4. 基于容器的适配器:​​std::stack​​是基于容器的适配器,它使用底层容器来存储元素。默认情况下,​​std::deque​​被用作底层容器,但你也可以选择其他容器,如​​std::vector​​或​​std::list​​。
  5. 快速插入和删除:由于​​std::stack​​是基于容器的适配器,它使用底层容器的插入和删除操作来实现元素的压入和弹出。这些操作的时间复杂度通常是常数时间,因此插入和删除操作非常高效。
  6. 无索引访问:​​std::stack​​不支持通过索引访问元素。你只能访问堆栈顶部的元素,即使用​​top()​​函数。如果你需要访问其他位置的元素,你需要先将顶部的元素弹出。
  7. 无迭代器支持:​​std::stack​​不支持迭代器,因此你不能使用迭代器遍历堆栈中的元素。如果你需要遍历堆栈中的元素,你需要先将它们弹出。
  8. 大小可变:​​std::stack​​的大小是可变的,你可以根据需要动态地压入和弹出元素。
  9. stack使用
  10. 包含头文件:首先,你需要包含​​​​​头文件,以便使用​​std::stack​​类。

    include 2. 创建堆栈对象:使用​​std::stack​​类创建一个堆栈对象。你需要指定堆栈中元素的类型。例如,如果你想创建一个存储整数的堆栈,你可以这样做:

    std::stack myStack;3. 压入元素:使用​​push(element)​​​函数将元素压入堆栈的顶部。你可以连续调用​​push()​​函数来压入多个元素。
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);4. 弹出元素:使用​​pop()​​函数从堆栈的顶部移除元素。你可以使用循环或条件语句来连续弹出元素。
    myStack.pop();5. 访问顶部元素:使用​​top()​​函数可以访问堆栈顶部的元素,但不会将其从堆栈中移除。
    int topElement = myStack.top();6. 检查堆栈是否为空:使用​​empty()​​​函数可以检查堆栈是否为空。如果堆栈为空,返回​​true​​​;否则返回​​false​​。
    if (myStack.empty()) {
    // 堆栈为空
    } else {
    // 堆栈不为空
    }7. 获取堆栈的大小:使用​​size()​​函数可以获取堆栈中元素的数量。
    int stackSize = myStack.size();这些是使用​​std::stack​​的一般步骤。可以根据需要进行堆栈的操作,如压入元素、弹出元素、访问顶部元素等。
    queue
  11. queue概念
    ​​queue的文档介绍​​
    在C++中,queue(队列)是一种数据结构,它遵循先进先出(FIFO)的原则。它类似于现实生活中的排队,新元素被添加到队列的末尾,而从队列中移除元素时,总是从队列的前端开始。
  12. queue特点
  13. 先进先出(FIFO):​​std::queue​​是一种先进先出的数据结构,这意味着最先添加到队列的元素将首先被移除。
  14. 基于容器的适配器:​​std::queue​​是基于容器的适配器,它使用底层容器来存储元素。
  15. 快速插入和删除:由于​​std::queue​​是基于容器的适配器,它使用底层容器的插入和删除操作来实现元素的添加和移除。这些操作的时间复杂度通常是常数时间,因此插入和删除操作非常高效。
  16. 无索引访问:​​std::queue​​不支持通过索引访问元素。你只能访问队列的前端和末尾元素,即使用​​front()​​和​​back()​​函数。
  17. 无迭代器支持:​​std::queue​​不支持迭代器。如果你需要遍历队列中的元素,你需要先将它们移除。
  18. 大小可变:​​std::queue​​的大小是可变的,你可以根据需要动态地添加和移除元素。
  19. queue使用
  20. 包含头文件:首先,你需要包含​​​​​头文件,以便使用​​std::queue​​类。

    include 2. 创建队列对象:使用​​std::queue​​类创建一个队列对象。你需要指定队列中元素的类型。例如,如果你想创建一个存储整数的队列,你可以这样做:

    std::queue myQueue;3. 添加元素:使用​​push(element)​​​函数将元素添加到队列的末尾。你可以连续调用​​push()​​函数来添加多个元素。
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);4. 移除元素:使用​​pop()​​函数从队列的前端移除元素。你可以使用循环或条件语句来连续移除元素。
    myQueue.pop();5. 访问前端和末尾元素:使用​​front()​​​函数可以访问队列的前端元素,使用​​back()​​函数可以访问队列的末尾元素,但不会将它们从队列中移除。
    int frontElement = myQueue.front();
    int backElement = myQueue.back();6. 检查队列是否为空:使用​​empty()​​​函数可以检查队列是否为空。如果队列为空,返回​​true​​​;否则返回​​false​​。
    if (myQueue.empty()) {
    // 队列为空
    } else {
    // 队列不为空
    }7. 获取队列的大小:使用​​size()​​函数可以获取队列中元素的数量。
    int queueSize = myQueue.size();这些是使用​​std::queue​​的一般步骤。可以根据需要进行队列的操作,如添加元素、移除元素、访问前端和末尾元素等。
    容器适配器
  21. 什么是适配器
    适配器是一种设计模式,它允许将一个类的接口转换为另一个类的接口,以便两个类可以协同工作。适配器模式通常用于解决两个不兼容的接口之间的问题。
    在C++中,适配器也可以指代标准库中的容器适配器。容器适配器是一种特殊类型的容器,它使用底层容器来提供不同的接口和功能。适配器通过封装底层容器的操作,提供了一组新的操作和语义。
  22. STL标准库中stack和queue的底层结构
    虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL标准库中​​std::stack​​​和​​std::queue​​​。它们分别基于底层容器(默认为​​std::deque​​)提供了堆栈和队列的功能。
  23. STL标准库中对于stack和queue的模拟实现
    ⭕stack的模拟实现
    template>
    class stack
    {
    public:
    //入栈
    void push(const T& x)
    {
     _con.push_back(x);
    
    }
    //出栈
    void pop()
    {
     _con.pop_back();
    
    }
    //返回栈顶数据
    T& top()
    {
     return _con.back();
    
    }
    //返回const类型栈顶数据
    const T& top() const
    {
     return _con.back();
    
    }
    //判断是否为空
    bool empty()
    {
     return _con.empty();
    
    }
    //返回栈的大小
    size_t size() const
    {
     return _con.size();
    
    }
    private:
    Container _con;
    };⭕stack的模拟实现
    template>
    class queue
    {
    public:
    //进入队列
    void push(const T& x)
    {
     _con.push_back(x);
    
    } //出队列
    void pop()
    {
     _con.pop_front();
    
    }
    //返回队尾数据
    T& back()
    {
     return _con.back();
    
    }
    //返回队头数据
    T& front()
    {
     return _con.front;
    
    }
    //返回const类型队尾数据
    const T& back() const
    {
     return _con.back();
    
    }
    //返回const类型队头数据
    const T& front() const
    {
     return _con.front;
    
    }
    //判断是否为空
    bool empty() const
    {
     return _con.empty();
    
    }
    //返回队列大小
    size_t size() const
    {
     return _con.size();
    
    }
    private:
    Container _con;
    };总结
    stack是一种后进先出(LIFO)的数据结构,它是一种容器适配器。它的特点是最后添加的元素将首先被移除。stack使用底层容器来存储元素,默认情况下使用std::deque作为底层容器。。queue是一种先进先出(FIFO)的数据结构,也是一种容器适配器。它使用底层容器来存储元素,默认情况下使用std::deque作为底层容器。适配器是一种设计模式,它允许将一个类的接口转换为另一个类的接口,以便两个类可以协同工作。在STL标准库中,stack和queue是基于其他容器实现的容器适配器。它们使用底层容器来存储元素,并提供了堆栈和队列的功能。
    温馨提示
    感谢您对博主文章的关注与支持!在阅读本篇文章的同时,我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章,可以点赞、评论和分享给您的同学,这将对我提供巨大的鼓励和支持。另外,我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新,不要错过任何精彩内容!
    再次感谢您的支持和关注。我们期待与您建立更紧密的互动,共同探索C++、算法和编程的奥秘。祝您生活愉快,排便顺畅!
目录
相关文章
|
24天前
|
存储 C++ 容器
C++入门指南:string类文档详细解析(非常经典,建议收藏)
C++入门指南:string类文档详细解析(非常经典,建议收藏)
32 0
|
5天前
|
C++
【C++成长记】C++入门 | 类和对象(下) |Static成员、 友元
【C++成长记】C++入门 | 类和对象(下) |Static成员、 友元
|
5天前
|
存储 编译器 C++
【C++成长记】C++入门 | 类和对象(中) |拷贝构造函数、赋值运算符重载、const成员函数、 取地址及const取地址操作符重载
【C++成长记】C++入门 | 类和对象(中) |拷贝构造函数、赋值运算符重载、const成员函数、 取地址及const取地址操作符重载
|
9天前
|
存储 编译器 C++
C++从遗忘到入门(上)
C++从遗忘到入门(上)
25 0
|
11天前
|
容器
|
12天前
|
编译器 C语言 C++
【C++】C++入门第一课(c++关键字 | 命名空间 | c++输入输出 | 缺省参数)
【C++】C++入门第一课(c++关键字 | 命名空间 | c++输入输出 | 缺省参数)
|
24天前
|
存储 编译器 C语言
C++入门: 类和对象笔记总结(上)
C++入门: 类和对象笔记总结(上)
31 0
|
2天前
|
存储 安全 C语言
【C++】string类
【C++】string类
|
存储 编译器 Linux
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
|
4天前
|
编译器 C++
标准库中的string类(上)——“C++”
标准库中的string类(上)——“C++”

热门文章

最新文章