【C++】stack、queue和deque(下)

简介: 【C++】stack、queue和deque(下)

5. 根据中缀表达式构建二叉树


其实将中缀表达式构建成二叉树的思路差不多,思路如下:


从左往右遍历中缀表达式

遇到操作数时,建立新节点存储该操作数并将该节点压入操作数栈中

当操作符从操作符栈中出栈时,为该操作符新建一个节点,并从操作数栈中 pop 出两个操作数节点,第一个操作数节点作为操作符节点的右孩子,第二个操作数节点作为操作符节点的左孩子,将新节点压入操作数栈中(注:节点 TreeNode 的值是 string,操作数栈存储的是 TreeNode*)。该过程直至操作符栈的栈顶操作符优先级小于当前操作符的优先级,最后将当前操作符压入操作符栈中。

注:操作符优先级关系同将中缀表达式转为后缀表达式的操作符优先级关系

当最后一个操作符出栈时,就构成了二叉表达树,且最后一个操作符节点为根节点

该二叉表达书的前序遍历就是前缀表达式(波兰表达式),中序遍历就是中缀表达式,后序遍历就是后缀表达式(逆波兰表达式)。


有些计算器就是通过将中缀表达式转化成后缀表达式,再计算后缀表达式求出结果。


6. 中缀表达式求值


给一个用字符串表示的中缀表达式数组,求出这个中缀表达式的值。


表达式只包含整数,+,-,*,/,(,)

ff4faf683d614b598a3889e95d032814.png

思路:


从左往右遍历中缀表达式

遇到操作数,将其放入操作数栈stack中

遇到左括号,直接将左括号放入操作符栈stack中

遇到右括号,操作符栈的元素出栈直至左括号成为栈顶元素。注意操作符栈元素出栈的过程中,操作数栈也要出两个操作数来进行计算,并将计算结果放回操作数栈中。最后左括号出栈

当遇到+ - * /操作符时,需比较操作符的优先级。如果栈顶操作符优先级高,则进行计算并将计算结果压入操作数栈中。最后弹出栈顶操作符并将当前操作符压入操作符栈中

遍历结束,将操作符栈和操作数栈中的元素进行计算。最后操作数栈的栈顶元素就是中缀表达式的计算结果


class Solution 
{
public:
    int evaluateExpression(vector<string> &expression) 
    {
        if(expression.size() == 0)
            return 0;
        stack<int> st1;  // 操作数栈
        stack<string> st2;  // 操作符栈
        for(auto& str : expression)    // 遍历中缀表达式
        {
            if(str == "(")  // 左括号直接入栈
                st2.push(str);
            else if(str == ")")
            {
                while(st2.top() != "(")
                {
                    calc(st1, st2);    // 操作符边出栈边计算
                    st2.pop();
                }
                st2.pop();  // 左括号出栈
            }
            else if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                while(!st2.empty() && compare(st2.top(), str))
                {
                    calc(st1, st2);
                    st2.pop();
                }
                st2.push(str);
            }
            else
                st1.push(stoi(str));    // 字符串转为操作数
        }
        // 将两个栈的剩余元素进行计算
        while(!st2.empty())
        {
            calc(st1, st2);
            st2.pop();
        }
        return st1.top();
    }
private:
    // 比较操作符优先级
    bool compare(const string& first, const string& second)
    {
        if(first == "(")    // 栈顶操作符为左括号,当前操作符直接入栈
            return false;
        else if(first == "*" || first == "/")
            return true;
        else if(second == "+" || second == "-")
            return true;
        else 
            return false;
    }
    // 计算
    void calc(stack<int>& st1, stack<string>& st2)
    {
        int right = st1.top();
        st1.pop();
        int left = st1.top();
        st1.pop();
        switch(st2.top()[0])
        {
            case '+':
                st1.push(left + right);
                break;
            case '-':
                st1.push(left - right);
                break;
            case '*':
                st1.push(left * right);
                break;
            case '/':
                st1.push(left / right);
                break;
        }
    }
};

9b7a22f8164c40c1b80741e2eb41daa9.png


7. 中缀表达式转化为前缀表达式


给定一个字符串数组,它代表一个表达式,返回该表达式的波兰表达式(去掉括号)。

a15e9d6159f44535b2d3ea109658d274.png

思路:


从右向左遍历中缀表达式

遇到数字,直接添加到vector ret的末尾

遇到右括号,入操作符栈stack st

遇到左括号,操作符栈元素出栈并添加到ret的末尾中,直至右括号弹出(右括号不添加到ret中)

如果遇到操作符,操作符栈弹栈至栈顶操作符不大于当前操作符,所有弹出的操作符依次添加到ret的末尾,最后再将该操作符入栈

出于方便,我们将所有操作符的优先级设置为:*/最高,+-次之,然后是右括号,最后是左括号

遍历完后,将操作符栈中的元素依次弹出并添加到ret的末尾。最后将ret反转就能得到前置表达式了


#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
class Solution
{
public:
  vector<string> Convertion(vector<string>& expression)
  {
    vector<string> ret;
    stack<string> st;
    for (int i = expression.size() - 1; i >= 0; --i)
    {
      string& str = expression[i];
      if (str == ")")    // 右括号直接入栈
        st.push(str);
      else if (str == "(")
      {
        while (st.top() != ")")
        {
          ret.push_back(st.top());
          st.pop();
        }
        st.pop(); // 右括号出栈
      }
      else if (str == "+" || str == "-" || str == "*" || str == "/")
      {
        // 栈顶操作符优先级大于当前操作符优先级,则出栈
        while (!st.empty() && getPriority(st.top()) > getPriority(str))
        {
          ret.push_back(st.top());
          st.pop();
        }
        st.push(str);
      }
      else    // 操作数则直接添加到ret的末尾
        ret.push_back(str);
    }
    // 栈中的操作符全部出栈
    while (!st.empty())
    {
      ret.push_back(st.top());
      st.pop();
    }
    reverse(ret.begin(), ret.end());  // 将ret反转得到前缀表达式
    return ret;
  }
private:
  int getPriority(const string& str)
  {
    if (str == "*" || str == "/")
      return 3;
    else if (str == "+" || str == "-")
      return 2;
    else if (str == ")")
      return 1;
    else
      return 0;
  }
};
int main()
{
  vector<string> expression1 = { "(", "5", "-", "6", ")", "*", "7" };
  vector<string> expression2 = { "3", "+", "(", "1", "-", "2", ")" };
  vector<string> ret1 = Solution().Convertion(expression1);
  vector<string> ret2 = Solution().Convertion(expression2);
  for (auto& str : ret1)
  {
    cout << str << " ";
  }
  cout << endl;
  for (auto& str : ret2)
  {
    cout << str << " ";
  }
  cout << endl;
  return 0;
}

26ab5f90c202493a92e68e081147060d.png


👉queue 的介绍和使用👈


queue 的介绍


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

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

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

empty:检测队列是否为空

size:返回队列中有效元素的个数

front:返回队头元素的引用

back:返回队尾元素的引用

push_back:在队列尾部入队列

pop_front:在队列头部出队列

标准容器类 deque 和 list 满足了这些要求。默认情况下,如果没有为 queue 实例化指定容器类,则使用标准容器 deque。

14b2aa9c4dab44ccb33cb065bb4fb0cd.png



queue 的使用


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



👉stack 的模拟实现👈


学习 stack 的模拟实现前,我们需要了解一下上面是设计模式。设计模式是一套被反复使用、多数人知晓的经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。


目前,我们学习到了一种设计模式 — 迭代器模式。迭代器模式不暴露底层的实现细节,封装后提供统一的方式访问容器。而接下来将要学习到的适配器模式就是将已有的东西封装转换成我们想要的东西。


stack 的适配器可以是 vector、list 和 deque,这些容器都支持尾插、尾删、判空和获得尾部元素等操作。stl 中的 stack 和 queue 的默认适配器都是双端队列 deque,而本人设计的 stack 默认适配器为 vector。注:双端队列将会在下面的内容里讲解。


// Stack.h
#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>
using namespace std;
namespace Joy
{
  // 默认容器为vector
  template <class T, class Container = vector<T> >
  class stack
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);
    }
    void pop()
    {
      _con.pop_back();
    }
    T& top()
    {
      return _con.back();
    }
    const T& top() const
    {
      return _con.back();
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}
// Test.cpp
#include "Stack.h"
int main()
{
  Joy::stack<int> st;
  st.push(1);
  st.push(2);
  st.push(3);
  st.push(4);
  st.push(5);
  while (!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
  return 0;
}


1675841718689.png


👉queue 的模拟实现👈


queue 的适配器需要支持头删、尾插、判空、获得头部元素和尾部元素等操作。因为 vector 没有pop_front头删接口且 vector 头删效率低,所以本人采用 list 作为 queue 的默认适配器。


// Queue.h
#pragma once
#include <deque>
#include <list>
#include <iostream>
using namespace std;
namespace Joy
{
  // 默认适配器为list
  template <class T, class Container = list<T> >
  class queue
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);
    }
    void pop()
    {
      _con.pop_front();
    }
    T& front()
    {
      return _con.front();
    }
    const T& front() const
    {
      return _con.front();
    }
    T& back()
    {
      return _con.back();
    }
    const T& back() const
    {
      return _con.front();
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}
// Test.cpp
#include "Queue.h"
int main()
{
  Joy::queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
  q.push(5);
  while (!q.empty())
  {
    cout << q.front() << " ";
    q.pop();
  }
  cout << endl;
  return 0;
}

53b3ca09f3cc48048c619b16cdb3c386.png

fe05664a9bcc45f1b242ed109041c682.png

👉容器适配器👈


什么是适配器


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

e5b32db5696b495988fa8ff9992d39a0.png


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


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

598ba994fc86471794348a2a39c6b39d.png

a5eeef48a859494b84aaf832c84b9149.png


deque


1. deque 的原理介绍


deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为 O(1)。与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。



deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态的二维

数组,其底层结构如下图所示:

502a3bca518d41e489511ec9b842f718.png

29c3da7de4564a8997fc4730619a2ee8.png

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

e02be76e9c454d21af73be86857b1a91.png


#include <deque>
#include <iostream>
using namespace std;
int main()
{
  deque<int> d;
  d.push_back(1);
  d.push_back(2);
  d.push_back(3);
  d.push_back(4);
  d.push_front(10);
  d.push_front(20);
  for (size_t i = 0; i < d.size(); ++i)
  {
    cout << d[i] << " ";
  }
  cout << endl;
  return 0;
}

374d411be9b44787b2333d8377fbb8f7.png


2. deque 的缺陷


与 vector 比较,deque 的优势是:头部插入和删除时,不需要搬移元素,效率高.而且在扩容时,也不需要搬移大量的元素,因此其效率是比 vector 高的。

与 list 比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。


但是,deque 有一个致命缺陷:不适合遍历,因为在遍历时,deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下。而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑 vector 和 list,deque 的应用并不多,而目前能看到的一个应用就是 STL 用其作为 stack 和 queue 的底层数据结构。deque 适用于中间插入删除少、头尾插入删除多、偶尔需要随机访问的场景。


性能对比


#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
// N个数据需要排序,vector+ 算法sort  deque+ sort
void Test()
{
  srand(time(0));
  const int N = 1000000;
  vector<int> v;
  v.reserve(N);
  deque<int> dq;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand();
    v.push_back(e);
    dq.push_back(e);
  }
  int begin1 = clock();
  sort(v.begin(), v.end());
  int end1 = clock();
  int begin2 = clock();
  sort(dq.begin(), dq.end());
  int end2 = clock();
  printf("vector sort:%d\n", end1 - begin1);
  printf("dequeue sort:%d\n", end2 - begin2);
}
int main()
{
  Test();
  return 0;
}


6483cb98c97b492b9c3383e1beb0c623.png


原因:deque 的随机访问效率没有 vector 的随机访问效率高。


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


stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back() 和 pop_back() 操作的线性结构,都可

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

push_back 和 pop_front 操作的线性结构,都可以作为queue 的底层容器,比如 list。但是 STL 中对 stack 和

queue 默认选择 deque 作为其底层容器,主要是因为结合了 deque 的优点,而完美的避开了其缺陷。


stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器),只需要在固定的一端或者两端进行操作。

在 stack 中元素增加时,deque 比 vector 的效率高(扩容时不需要搬移大量数据);queue 中的元素增加时,deque 不仅效率高,而且内存使用率高。


👉总结👈


本篇博客主要讲解了栈的几道经典例题:最小值、验证栈序列、逆波兰表达式求值和将中缀表达式转为后缀表达式、什么是适配器、以适配器模式实现 stack 和 queue 以及双端队列 deque 等等。那么以上就是本篇博客的全部内容了,如果大家觉得有收获的话,可以点个三连支持一下!谢谢大家!💖💝❣️





















相关文章
|
16天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
50 21
|
4月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
60 1
|
4月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
60 1
|
4月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
99 0
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
67 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
46 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
48 5
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
38 5
|
1月前
|
Serverless 编译器 C++
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
47 4
|
1月前
|
设计模式 IDE 编译器
【C++面向对象——类的多态性与虚函数】编写教学游戏:认识动物(头歌实践教学平台习题)【合集】
本项目旨在通过C++编程实现一个教学游戏,帮助小朋友认识动物。程序设计了一个动物园场景,包含Dog、Bird和Frog三种动物。每个动物都有move和shout行为,用于展示其特征。游戏随机挑选10个动物,前5个供学习,后5个用于测试。使用虚函数和多态实现不同动物的行为,确保代码灵活扩展。此外,通过typeid获取对象类型,并利用strstr辅助判断类型。相关头文件如&lt;string&gt;、&lt;cstdlib&gt;等确保程序正常运行。最终,根据小朋友的回答计算得分,提供互动学习体验。 - **任务描述**:编写教学游戏,随机挑选10个动物进行展示与测试。 - **类设计**:基类
32 3