1、栈与队列理论基础

栈是先进后出，队列是先进先出
如图所示：

那么我在这里列出四个关于栈的问题，大家可以思考一下。以下是以C++为例，相信使用其他编程语言的同学也对应思考一下，自己使用的编程语言里栈和队列是什么样的。

1. C++中 stack 是容器吗？
2. 我们使用的 stack 属于哪个版本的 STL？
3. 我们使用的 STL 中的 stack 是如何实现的？
4. stack 提供迭代器来遍历 stack 空间吗？

相信这四个问题并不那么好回答，因为一些同学使用数据结构会停留在非常表面上的应用，稍稍往深一问，就会有好像懂，好像也不懂的感觉。

有的同学可能仅仅知道有栈和队列这么个数据结构，却不知道底层实现，也不清楚所使用栈和队列和STL是什么关系。
所以这里我在给大家扫一遍基础知识，
首先大家要知道 栈 和 队列 是STL（C++标准库）里面的两个数据结构。

C++标准库是有多个版本的，要知道我们使用的 STL 是哪个版本，才能知道对应的栈和队列的实现原理。
那么介绍一下，三个最为普遍的 STL 版本：

1. HP STL 其他版本的C++ STL，一般是以 HP STL 位蓝本实现出来的，HP STL 是C++ STL的第一个实现版本，而且是开放源代码。
2. P.J.Plauger STL 由 P.J.Plauger参照 HP STL 实现出来的，被 Visual C++ 编译器所采用，不是开源的。
3. SGI STL 由 Silicon Graphics Computer Systems 公司参照 HP STL实现，被 Linux 的C++编译器 GCC 所采用，SGI STL 是开源软件，源码可读性甚高。

接下来介绍的栈和队列也是 SGI STL 里面的数据结构，知道了使用版本，才知道对应的低层实现。来说一说栈，栈先进后出，如图所示：

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？
从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列，只要封住一端，只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

我们也可以指定vector为栈的底层实现，初始化语句如下：

std::stack<int, std::vector<int>> third;    // 使用vector为低层容器的栈

刚刚讲过栈的特性，对应的队列的情况是一样的。
队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为其底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third;         // 定义以list为底层容器的队列

所以 STL 队列也不被归类为容器，而被归类为 container adapter（容器适配器）。

我这里讲的都是 C++ 语言中的情况，使用其他语言的同学也要思考栈与队列的底层实现原理，不要对数据结构的使用浅尝辄止，而要深挖其内部原理，才能夯实基础。

1.1、栈提供的函数接口

和其他序列容器相比，stack 是一类存储机制简单、所提供操作较少的容器。下面是 stack 容器可以提供的一套完整操作：

• top（）返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
• push（const T& obj）：可以将对象副本压入栈顶。这时通过调用低层容器的 push_back（）函数完成的。
• push（T&& obj）：以移动对象的方式将对象压入栈顶。这是通过调用低层容器的有右值引用参数的 push_back() 函数完成的
• pop（）：弹出栈顶元素
• size（）：返回栈中元素的个数
• empty（）：在栈中没有元素的情况下返回true
• emplace（）：用传入的参数调用构造函数，在栈顶生成对象【更加高效的push_back()】
• swap（stack & other_stack）：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈中的相同。对于stack对象有一个特例化的全局函数 swap（）可以使用。

头文件：#include<stack>

1.2、队列提供的函数接口

STL 中队列（queue）的使用方法
基本操作：

• push（x）将x压入队列的末端
• pop（）弹出队列的第一个元素（队顶元素），注意此函数并不返回任何值
• front（）返回第一个元素（队顶元素）
• back（）返回最后被压入的元素（队尾元素）
• empty（）当队列为空时，返回true
• size（）返回队列的长度

使用方法：
头文件：
#include<queue>
声明方法：

1. 普通声明 queue<int> q;
2. 结构体 struck node {...}; queue<node> q;

2、用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）
这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
下面动画模拟以下队列的执行过程如下：
执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

C++代码如下：

class MyQueue {
public:
    // 用一个输入栈和一个输出栈来模拟一个队列
    stack<int> isStack;
    stack<int> osStack;
    MyQueue() {
    }
    void push(int x) {
        isStack.push(x);
    }
    int pop() {
        if(osStack.empty()){
            while(isStack.empty() == false){
                osStack.push(isStack.top());
                isStack.pop();
            }
        }
        int result = osStack.top();
        osStack.pop();
        return result;
    }
    // 返回队列的第一个元素
    int peek() {
        int result = this->pop();
        osStack.push(result);
        return result;
    }
    bool empty() {
        if(isStack.empty() && osStack.empty()){
            return true;
        }
        return false;
    }
};
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

3、用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

思路：
（这里要强调是单向队列）
有的同学可能疑惑这种题目有什么实际工程意义，其实很多算法题目主要是对知识点的考察和教学意义远大于其工程实践的意义，所以面试题也是这样！

刚刚做过栈与队列：我用栈来实现队列怎么样？(opens new window)的同学可能依然想着用一个输入队列，一个输出队列，就可以模拟栈的功能，仔细想一下还真不行！

队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！

如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

class MyStack {
public:
    queue<int> queue1;      // queue1用来存储push进去的元素
    queue<int> queue2;      // queue2作为中间桥梁
    MyStack() {
    }
    void push(int x) {
        queue1.push(x);
    }
    int pop() {
        int size = queue1.size();
        size--;     // 保留queue1中最后压入的元素
        while(size--){
            queue2.push(queue1.front());
            queue1.pop();
        }
        while(!queue2.empty()){
            queue1.push(queue2.front());
            queue2.pop();
        }
        int result = queue1.front();    // 这个时候第一个元素是原来的最后一个元素
        queue1.pop();
        return result;
    }
    int top() {
        return queue1.back();       // stack的第一个就是queue的最后一个
    }
    bool empty() {
        if(queue1.empty() && queue2.empty()){
            return true;
        }
        return false;
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

4、有效的括号

20. 有效的括号 - 力扣（LeetCode）

思路
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。
建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。
先来分析一下 这里有三种不匹配的情况，

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。
3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
动画如下：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
分析完之后，代码其实就比较好写了，
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

class Solution {
public:
    bool isValid(string s) {
        // 三种情况是无效的字符串
        // 1.相应的位置的括号匹配不上
        // 2.左括号多余，即栈外中找不到匹配的右括号
        // 3.右括号多余，即栈中没有字符串与之匹配
        stack<char> strStack;
        for(int i = 0; i < s.size(); i++){
            // 如果是左括号、左中括号、左花括号，都入栈
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                strStack.push(s[i]);
                continue;
            }
            // 遇到右括号、右中括号、右花括号，就出栈，然后与之相比较
            if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
                if(strStack.empty() == false){
                    if((strStack.top() == '(' && s[i] == ')') || (strStack.top() == '[' && s[i] == ']')
                        || (strStack.top() == '{' && s[i] == '}')){
                        strStack.pop();
                        continue;
                    }
                    else{                           // 情况1
                        return false;
                    }
                }
                else if(strStack.empty() == true){   // 情况2
                    return false;
                }
            }
        }
        if(strStack.empty() == false){               // 情况3
            return false;
        }
        return true;
    }
};

代码随想录的代码比我写的简洁很多，可以看看代码随想录 - 栈与队列 - 4. 有效的括号

5、删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

思路：
会做上面的有效的括号这道题就会做这道题，但有一个点需要注意，想要把知道题做到极致，就不要开辟辅助空间，即要求时间复杂度为O(n)，空间复杂度为O(1)；我认为我这道题写的比代码随想录中的要好。😀😀😀

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> str_stack;
        for(int i = s.size() - 1; i >= 0; i--){     // 之所以从字符串尾部开始入栈，是为了保证出栈的时候字符串是正序的
            if(!str_stack.empty()){
                if(str_stack.top() != s[i]){
                    str_stack.push(s[i]);
                }
                else{
                    str_stack.pop();
                }
            }
            else{
                str_stack.push(s[i]);
            }
        }
        int count = 0;          // count记录删除重复字符后的字符串长度
        while(!str_stack.empty()){
            s[count] = str_stack.top();
            str_stack.pop();
            count++;
        }
        s.resize(count);        // resize后的字符串才是我们真正需要的字符串
        return s;
    }
};

6、逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

思路：
在上一篇文章中1047.删除字符串中的所有相邻重复项(opens new window)提到了 递归就是用栈来实现的。
所以栈与递归之间在某种程度上是可以转换的！ 这一点我们在后续讲解二叉树的时候，会更详细的讲解到。
那么来看一下本题，其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。

但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了，就可以了。

在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和1047.删除字符串中的所有相邻重复项(opens new window)中的对对碰游戏是不是就非常像了。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i = 0; i < tokens.size(); i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num1 + num2);
                else if(tokens[i] == "-") st.push(num2 - num1);
                else if(tokens[i] == "*") st.push(num1 * num2);
                else if(tokens[i] == "/") st.push(num2 / num1);
            }
            else{
                st.push(stoi(tokens[i]));
            }
        }
        int result = st.top();
        return result;
    }
};

注意：这道题有两个知识点需要思考

1. 什么时候用''，什么时候用 ""，这个可不能混淆。
2. stoi函数和 atoi函数

   6.1、’ ‘ 和 “ “

单引号是字符型，双引号是字符串类型
单引号引起的一个字符实际上代表一个整数。
双引号引起的字符串，代表的却是一个指向无名数组起始字符的指针。该数组会被双引号之间的字符以及一个额外的二进制为零的字符 '\0'初始化。

6.2、stoi函数和atoi函数

作用：

• 如果我们想要把一个string类型的字符串或者存放在一个字符数组（char* 类型）中的字符串转换为数字的化，我们通常会需要用到 stoi 函数和 atoi 函数。

头文件：

• stoi 函数和 atoi 函数的头文件都是 #include<string>（c++）

stoi（）函数参数

• stoi（）参数是 const string&类型的，因此可以将一个 string 类型的字符串转换成一个数字。返回值类型是 int 型

atoi（）函数参数

• atoi（）参数是 const char*类型的，因此可以将一个字符数组转换成一个数字。但是如果将一个 string 类型的字符串转换成数字的话，这时我们需要先调用 string 类成员方法 .c_str()将起转换为 const char* 类型后，再进行转换。atoi 函数的返回值为 int 类型。

atoi（）函数和stoi（）函数的注意事项：

1. stoi（）会做范围检查，默认范围在 int 范围内（因为返回的是int类型），如果超出范围的话会 runtime error！
2. atoi（）则不会做范围检查，如果超出范围的话，超出上界，则输出上界；超出下界，则输出下界。

例如：

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main(){
    string str = "333333333333333333";
    // atoi()会返回上or下界（当转换的数字超出int范围时）
    cout << atoi(str.c_str()) <<endl;
    // stoi()返回out_of_range(超出边界异常）
    cout << stoi(str) << endl;
}

1. atoi（）和stoi（）函数都是只转换字符串的数字部分，如果遇到其他字符的话，则停止转换。请看代码：

   #include <cstdio>
   #include <iostream>
   #include <string>
   using namespace std;
   int main(){
    char str[] = {'1','2','a','3'};
    string str1 = "12aa3";
    //遇到了'a'字符，停止数字转换
    cout << atoi(str) << endl;
    //遇到了'a'字符，停止数字转换
    cout << stoi(str1) << endl;
   }

   

7、滑动窗口最大值（困难）

239. 滑动窗口最大值 - 力扣（LeetCode）

这道题很巧妙！！！思路很好
题解太长了，建议看：代码随想录 - 栈与队列 - 7.滑动窗口最大值，里面的题解详细的不得了！

这道题暴力解法没什么好说的，垃圾解法，是个人就会写。

还得是队列求解！

class Solution{
public:
    class MyQueue{        // 自定义一个单调队列（从大到小）
    public:
        deque<int> que;    // 使用deque来实现单调队列
        // 每次弹出之前，比较要弹出的值是否与队列中的front相等，如果相等则弹出
        // pop之前需要判断队列是否为空
        void pop(int value){
            if(!que.empty() && value == que.front()){
                que.pop_front(value);
            }
        }
        // 如果push的数值大于处于队列入口元素的数值，那么将队列末尾的数值弹出（保证队列从大到小排序）
        // 直到push的数值小于队列入口的数值
        void push(int value){
            while(!que.empty() && value > que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }
        // 弹出队列首部，即获得队列中的最大值
        int front(){
            if(!que.empty()){
                return que.front();
            }
            return INT_MAX;
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k){
        Myqueue que;
        vector<int> result;
        for(int i = 0; i < k; i++){        // 将前k个元素存入队列中(注意！队列中不一定真的有k个元素，有一些可能被pop了)
            que.push(nums[i]);
        }
        result.push_back(que.front());    // 记录前k个元素的最大值
        for(int i = k; i < nums.size(); i++){
            que.pop(nums[i - k]);        // 滑动窗口移除最前面的元素
            que.push(nums[i]);            // 滑动窗口后加入新的元素
            result.push_back(que.front());    // 记录当前窗口的最大值
        }
        return result;
    }
};

在来看一下时间复杂度，使用单调队列的时间复杂度是 $O(n)$。
有的同学可能想了，在队列中 push元素的过程中，还有pop操作呢，感觉不是纯粹的$O(n)$。
其实，大家可以自己观察一下单调队列的实现，nums 中的每个元素最多也就被 push_back 和 pop_back 各一次，没有任何多余操作，所以整体的复杂度还是 $O(n)$。
空间复杂度因为我们定义一个辅助队列，所以是$O(k)$。

扩展

大家貌似对单调队列 都有一些疑惑，首先要明确的是，题解中单调队列里的pop和push接口，仅适用于本题哈。单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。 不要以为本地中的单调队列实现就是固定的写法哈。
大家貌似对deque也有一些疑惑，C++中deque是stack和queue默认的底层实现容器（这个我们之前已经讲过啦），deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。

8、前k个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

思路：
这道题主要涉及到如下三个内容：

1. 要统计元素出现的频率
2. 对频率排序
3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用 map 来进行统计。
然后是对频率进行排序，这里我们可以使用一种 容器适配器 就是 优先级队列来解决。

什么是优先级队列呢？
其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？
缺醒情况下priority_queue利用max-heap（大顶堆）完成元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，数种每个节点的值都不小于（或不大于）其左右孩子的值，如果父节点是大于等于左右孩子的就是大顶堆，小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的画就直接用 priority_queue（优先级队列）就可以了，低层实现都是一样的，从小到大就是小顶堆，从大到小就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。
为什么不用快速排序呢？使用快排要将map转换成vector的结构，然后对整个数组进行排序，而这种场景下，我们其实只需要维护K个有序的序列就可以了，所以使用优先级队列是最优的。

此时要思考一下，是使用小顶堆呢？还是使用大顶堆？
有的同学一想，题目要求前K个高频元素，那么果断使用大顶堆啊！
那么问题来了，定义一个大小为K的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的值弹出去了，那么怎么保留下来前K个高频元素呢？
而且使用大顶堆就要把所有元素都进行排序，那能不能只排序K个元素呢？

所以我们要用小顶堆，因为要统计最大前K个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里累计的才是前K个最大元素。

寻找前K个最大元素流程如图所示：（图中的频率只有三个，所以正好构成一个大小为3的小顶堆，如果频率更多一些，则用这个小顶堆进行扫描）

看代码之前有必要先直到 优先级队列 各个参数的含义：

• typename是数据的类型；
• container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；
• functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

[

](https://blog.csdn.net/jay_zzs/article/details/106549621)

C++代码如下：

class Solution{
public:
    // 自定义一个小顶堆
    class Mycomparison{
    public:
        // 重写priority_queue<typename, container, functional>中的functional方法
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
            return lhs.second > rhs.second;        // 小顶堆是以 pair.second 为权重进行比较的(即比较map中的second的值)
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k){
        unordered_map<int, int> map;
        // 要统计元素出现的频率
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }
        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, Mycomparison> pri_que;
        for(unordered_map<int, int>::iterator iter = map.begin(); iter != map.end(); iter++){
            pri_que.push(*iter);
            if(pri_que.size() > k){        // 如果堆的大小大于k，那么将弹出队头元素，保证堆的大小为K
                pri_que.pop();
            }
        }
        vector<int> result(k);        // 定义一个范围在[0,k)的vector
        for(int i = k - 1; i >= 0; i--){
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

优先级队列详解

C++——优先级队列（priority_queue）

C++ pair的基本用法总结（整理）

9、简化路径

71. 简化路径 - 力扣（LeetCode）

9.1、C++move()函数

要了解move函数首先要弄清楚左值引用和右值引用

左值、左值引用、右值、右值引用

1. 左值和右值的概念

• 左值是可以放在赋值号左边可以被赋值的值；左值必须要在内存中有实体；
• 右值是在赋值号右边取出值赋给其他变量的值；右值可以在内存也可以在CPU、寄存器中；

一个对象被用作右值时，使用的是它的内容（值），被当作左值时，使用的是它的地址。

1. 引用

引用是C++语法做的优化，引用的本质还是考指针来实现的。引用相当于变量名的别名。
引用可以改变指针的指向，还可以改变指针所指向的值。

引用的基本规则：

1. 声明引用的时候必须初始化，且一旦绑定，不可把引用绑定到其他对象；即引用必须初始化，不能对引用重定义！
2. 对引用的一切操作，就相当于对原对象的操作。

1. 左值引用和右值引用
   1. 左值引用
      1. 左值引用的基本语法：type &引用名 = 左值表达式
   2. 右值引用
      1. 右值引用的基本语法：type &&引用名 = 右值表达式
      2. 右值引用在企业开发人员在代码优化方面会经常用到。
      3. 右值引用的 &&中间不可以有空格

• std::move并不能移动任何东西，它唯一的功能是将一个左值强制转化为右值引用，继而可以通过右值引用使用该值，以用于移动语义。从实现上将，std::move基本等同于一个类型转换：static_cast<T &&>(value);
• C++标准库使用，比如 vector::push_back 等这类函数时，会对参数的对象进行复制，连数据也会复制，这就会造成对象内存的额外创建，本来原意时想把参数 push_back 进来就行了，通过 std::move，可以避免不必要的拷贝操作。
• std::move 就是为性能而生
• std::move 是将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有内存的搬迁或者内存拷贝。

用法：
原value值被move 之后值被转移，所以为空字符串

#include <iostream>
#include <utility>
#include <vector>
#include <string>
int main(){
    std::string str = "Hello";
    std::vector<std::string> v;
    // 调用常规的拷贝构造函数，新建字符数组，拷贝数据
    v.push_back(str);
    std::cout << "After copy, str is \"" << str << "\"\n";
    // 调用移动构造函数，掏空str，掏空后，最好不要使用str
    v.push_back(std::move(str));
    std::cout << "After move, str is \"" << str << "\"\n";
    std::cout << "The contents of the vector are \"" << v[0]
                                         << "\", \"" << v[1] << "\"\n";
}

输出:

After copy, str is "Hello"
After move, str is ""
The contents of the vector are "Hello", "Hello"

9.2、言归正传

在简化路径这道题上，需要考虑两个问题

1. 如何将题目给的字符串path分割为一个一个的独立的字符串，例如：path = “/home/user/.././apps/…//“；我们需要把它分割为 “home”，”user”，”..”，”.”，”apps”，”…”，””
2. 在问题1的基础上，需要考虑三种情况
   1. 如果是正常的文件名，我们把它入栈
   2. 如果是 “” 或者 “.”，我们不必做任何操作
   3. 如果是 “..”，我们判断栈是否空，不为空则弹出栈顶元素

class Solution{
public:
    string simplifyPath(string path){
        // 我们需要根据自己的需求重写split函数
        auto split = [](const string& s, char delim) -> vector<string> {
            vector<string> ans;        // ans存储的是一个个的字符串
            string cur;
            for(char ch : s){
                if(ch == delim){
                    ans.push_back(std::move(cur));
                    cur.clear();    // 将字符串的内容情况，使源字符串称为一个空字符串(长度为0个字符)
                }
                else{
                    cur += ch;
                }
            }
            ans.push_back(std::move(cur));    // 处理边界情况,即将最后一个字符串入栈
            return ans;
        };
        vector<string> names = split(path, '/');
        vector<string> stack;
        for(string& name: names){
            if(name == ".."){
                if(!stack.empty()){        // ???为什么不能是 if(name == ".." && !stack.empty())
                    stack.pop_back();
                }
            }
            else if(!name.empty() && name != "."){
                stack.push_back(std::move(name));
            }
        }
        string ans;
        if(stack.empty()){
            ans = "/";
        }
        else {
            for(string& name : stack){
                ans += "/" + std::move(name);
            }
        }
        return ans;
    }
};

10、栈与队列总结

代码随想录 - 栈与队列 - 9.栈与队列总结