【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现(二)

简介: 【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现

【C++】C++ STL探索:容器适配器 Stack 与 Queue 的使用及模拟实现(一)https://developer.aliyun.com/article/1617374


三、容器适配器

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

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

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

4.1 deque

在模拟实现之前,这里先简单介绍deque容器

4.1.2 deque介绍

deque(双端队列):是一种双开可口得"连续"空间数据结构

双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度O(1),与vector比较,头插效率高,不需要搬移元素,在扩容时,也不需要搬运大量的数据;与list比较,空间利用率比较高,不需要存储额外的字段

但是deque并不是真的连续的空间,而是由一段连续的小空间拼接而成的,实际上deque类似于一个动态的二维数组,其底层结构如下:

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其"整体连续"以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计比较复杂

那deque是如何借助其迭代器维护其假想连续的结构呢?

4.1.3 deque的缺陷

不适合遍历,因为在遍历时,deque的迭代器需要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而且在序列场景中,可能需要经常遍历。因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目能看到的一个应用就是,STL用其作为stack和queue的底层数据结构

4.1.4 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以

queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。

但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷。
  3. deque结合vector和list有点,但是在遍历方面存在缺陷和实现复杂问题上,stack与queue使用deque作为底层容器属于扬长避短手段

五、模拟实现Stack与queue

5.1 Stack.h

#pragma once
#include <vector>
namespace  bit
{
  template<class T, class Container = vector<T>>
  class Stack
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_back();
    }
  private:
        //容器适配器
    Container _con;
  };
  void test1()
  {
    Stack<int> st;
  }
}

5.2 Queue.h

#pragma once
#include <list>
#include <deque>
namespace bit
{
    template<class T, class Container = deque<T>>
        class queue
        {
            public:
            void push(const T& x)
            {
                _con.push_back(x);
            }
            void pop()
            {
                _con.pop_front();
            }
            size_t size()
            {
                return _con.size();
            }
            bool empty()
            {
                return _con.empty();
            }
            const T& back()
            {
                return _con.back();
            }
            const T& front()
            {
                return _con.front();
            }
            private:
            Container _con;
        };
    void test()
    {
        queue<int> q;
        q.push(1);
        cout << q.back() << endl;
        q.push(2);
        cout << q.back() << endl;
        q.push(3);
        cout << q.back() << endl;
    }
}

以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二呀C++笔记,希望对你在学习C++语言旅途中有所帮助!

目录
打赏
0
0
0
0
21
分享
相关文章
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 的奥秘,从入门到高效编程
|
27天前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
58 21
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
47 1
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等