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

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

一、Stack

1.1 stack介绍

stack文档介绍

  1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入和提取操作
  2. stack是作容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素的,将特定类作为其底层,元素特定容器的尾部(即是栈顶)被压入和弹出
  3. stack的底层容器可以是任何标准的容器类名模板或者一些特定的容器类,这些容器类应该支持以下操作
  • empty:判空操作
  • back:获取尾部元素操作
  • push_back:尾部插入元素操作
  • pop_back:尾部删除元素操作
  1. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

1.2 stack容器使用

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

1.3 关于stack使用场景

1.3.1 最小栈

class MinStack
{
    public:
    /** initialize your data structure here. */
    void push(int x) 
    {
        _st.push(x);
        if(_minst.empty() || x <= _minst.top())
        {
            _minst.push(x);
        }
    }
    void pop()
    {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    int top() 
    {
        return _st.top();
    }
    int getMin() 
    {
        return _minst.top();
    }
    private:
    stack<int> _st;
    stack<int> _minst;
};

具体流程:

  1. 创建一个栈,设置min的变量记录最小值。但是效率很低,如果插入或者删除数据,又需要重新遍历
  2. 我们可以创建两个栈,一个用于插入或删除数据,一个用于记录栈中最小数。
  3. 如果插入的数据比最小栈中栈顶数据要小,就插入在最小栈栈顶中。如果删除数据跟最小栈数据一样,需要同步删除,保持对其;如果删除数据不等于最小栈数据,单纯删除一边数据。

1.3.2 栈的弹出压入序列

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{
    stack<int> st;
    int pushi = 0; int popi = 0;
    while(pushi < pushV.size())
    {
        st.push(pushV[pushi++]);
        while(!st.empty() && st.top() == popV[popi])
        {
            popi++;
            st.pop();
        }
    }
    return st.empty();
}

具体思路:

  1. 入栈序列不断入栈,在入栈期间判断栈顶元素和出栈序列是否匹配
  2. 如果匹配,就需要持续出数据,直到不匹配或者栈为空(不一定结束)
  3. 如果不匹配,那就继续入栈,等待下次匹配或结束
  4. 结束标志:入栈序列走完后
  5. 结果判断:栈不为空

1.3.3 何为中缀和后缀表达式

我们在实际中一般采用的是中缀表达式a+(b-c),而后缀表达式是采用操作数、操作数、操作符的结构,转为这种形式的原因,是提供计算机使用的,中缀表达式给人看,一眼知道运算顺序,但是计算机不知道,需要转化后缀表达式进行运算(观察蓝色一圈圈圈起来的部分),遇到操作符就开始跟前面两操作数进行运算,返回一个数值。

1.3.4 逆波兰(后缀)表达式求值

class Solution
 {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        set<string> s = {"+","-","*","/"};
        
        for(auto str : tokens)
        {
            //如果等于操作符进行运算符
            if(s.find(str) != s.end())
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                     case '-':
                        st.push(left-right);
                        break;  
                    case '*': 
                        st.push(left * right);
                        break;  
                    case '/':
                        st.push(left / right);
                        break;      
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

具体流程:

  1. 根据后缀表达式的工作原理,可以很快按照逻辑解决这道题目
  2. 首先遇到操作符先入栈,如果遇到操作符就出栈两个操作数进行四则运算,并将结果入栈,等待下一次运算
  3. 这里采用了set容器和stoi函数,简单介绍这两个函数的作用。
  4. set是一个集合容器,存储唯一的元素,并且按照特定的顺序进行排序。
  5. 使用s.find(str)时。从集合s中查找字符串str。如果str存在s集合中,find函数会返回一个指向该元素的迭代器,否则会返回s.end(),表达未找到该元素
  6. stoi函数将字符串转换为整数,将一个标识数字的字符串转化为对应的整数类型,比如将"123"转化为整数123

1.3.5 中缀表达式转化为后缀表达式

  • 中缀表达式:1 + 2 * 3 - 4
  • 后缀表达式:1 2 3 * + 4 -

办法:

  1. 操作数输出
  2. 操作符
  • 当栈为空,入栈
  • 比栈顶的操作符优先级高,入栈
  • 比栈顶的操作符优先级低或者相等,出栈操作符
  1. 结束后,将栈中操作符,全部出栈

说明:这里关键为操作符,操作符出栈必有两个操作数在前面。同时存在两个操作符在栈中说明前面有三个操作符,即存在操作符的优先性。这里优先性是通过栈得以实现,优先级高的操作符先出栈。至于操作符的结合性就落到比栈顶的操作符优先级相等出栈操作符这块了。

1.3.6 深入探索:复杂表达式

如果是一个复杂的表达式,如何从中缀转化后缀表达式,进行运算呢?

例子: 1+2*(3+4/(2-1)+6)+5

办法:括号走递归,解决括号中表达式问题,将括号中顺序问题解决再添加到原本表达式中。

二、Queue

2.1 queue介绍

队列文档介绍

  1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素(元素从队尾入队列,从队头出队列)
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设置的容器类。该底层应该至少支持以下操作
  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:返回队尾元素的引用
  • pop_front:在队列头部出队列
  1. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。(这里容器选择不适合vector,因为没有头删,如果使用erase效率也很低)

2.2 queue使用

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


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

目录
打赏
0
0
0
0
21
分享
相关文章
|
23天前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
54 21
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
41 1
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
68 7
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
66 0
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
50 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
50 5
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
40 5

热门文章

最新文章