C++算法学习五.栈与队列

根据代码随想录，记录学习一些算法经验?

1.栈与队列的理论基础

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

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器,?SGI STL中队列一样是以deque为缺省情况下的底部结构。

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

2.用栈实现队列（232题）

题目描述：

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

模拟题：使用两个栈来模拟即可实现，一个栈是输入栈，另一个是输出栈，注意弹出队列元素时候，要注意首先看输出栈是否为空，在看输入栈是否为非空，不为空全部压入栈中在弹出。

class MyQueue {
public:
    stack<int>stIn;//输入栈
    stack<int>stOut;//输出栈
    MyQueue() {

    }
    
    void push(int x) {//压入队列，其实就是输入栈进栈
        stIn.push(x);
    }
    
    int pop() {//弹出队列
        if(stOut.empty()){//输出栈为空
            while(!stIn.empty()){//输入栈不为空
                stOut.push(stIn.top());//把全部输入栈压入到输出栈中
                stIn.pop();//弹出输出栈的元素
            }
        }
        int result = stOut.top();//结果就是输出栈弹出的元素
        stOut.pop();//弹出元素
        return result;
    }
    
    int peek() {//队头元素
        int res = this->pop();//复用了Pop函数
        stOut.push(res);
        return res;
    }
    
    bool empty() {//判断是否为空，两个栈都空即为空
        return stIn.empty() && stOut.empty();
    }
};

• 时间复杂度: push和empty为O(1), pop和peek为O(n)
• 空间复杂度: O(n)

3.用队列实现栈（225题）

题目描述：

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

使用两个队列做法：一个队列实际操作，另一个队列进行辅助，下面实现代码：

class MyStack {
public:
    queue<int>que1;//两个队列实现，队列2实现辅助 功能
    queue<int>que2;//

    MyStack() {

    }
    
    void push(int x) {
        que1.push(x);//队列的压入就是相当于压栈
    }
    
    int pop() {//弹出元素
        int size = que1.size();//计算队列的大小
        size--;//先做一个减一操作留一个元素
        while(size--){//将队列1转队列2中，队列1的头的元素压入队列2，再弹出
            que2.push(que1.front());
            que1.pop();
        }
        int result = que1.front();//队列1剩下的元素就是要弹出的元素
        que1.pop();//弹出
        que1 = que2;//队列2赋值给队列1
        while(!que2.empty()){//清空队列2 
            que2.pop();
        }
        return result;//返回值
    }
    
    int top() {//队列尾就是栈头元素
        return que1.back();
    }
    
    bool empty() {//队列1空了栈空
        return que1.empty();
    }
};

队列2也就是在弹出元素作为辅助作用，

• 时间复杂度: pop为O(n)，其他为O(1)
• 空间复杂度: O(n)

下面用一个队列实现的：一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

class MyStack {
public:
    queue<int>que1;//1个队列实现

    MyStack() {

    }
    
    void push(int x) {
        que1.push(x);//队列的压入就是相当于压栈
    }
    
    int pop() {//弹出元素
        int size = que1.size();//计算队列的大小
        size--;//先做一个减一操作留一个元素
        while(size--){//将队列1的头的元素压入队列1尾，再弹出
            que1.push(que1.front());
            que1.pop();
        }
        int result = que1.front();//队列1剩下的元素就是要弹出的元素
        que1.pop();//弹出
        return result;//返回值
    }
    
    int top() {//队列尾就是栈头元素
        return que1.back();
    }
    
    bool empty() {//队列1空了栈空
        return que1.empty();
    }
};

• 时间复杂度: pop为O(n)，其他为O(1)
• 空间复杂度: O(n)

4.有效的括号?（20题）

题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

• 输入: "()"
• 输出: true

?使用栈来解法：括号匹配是典型栈解法应用，栈一般用来做对称匹配题目，需要注意字符串不匹配的情况，三种情况：左括号多余，括号不匹配，右括号多余，技巧：匹配左括号，右括号进栈，最后对比是否相等就可以，遇左进栈，遇右弹出比较。

class Solution {
public:
    bool isValid(string s) {
        stack<int>st;//申请一个栈
        for(int i = 0;i < s.size(); i++){//遍历整个字符串
            if(s[i] == '('){//遇到左括号全部把右括号压入栈
                st.push(')');
            }else if(s[i] == '{'){
                st.push('}');
            }else if(s[i] == '['){
                st.push(']');
            }else if(st.empty() || s[i] != st.top()){//判断右括号多余和括号不匹配的情况
                return false;
            }else{//相等弹出括号
                st.pop();
            } 
        }
        return st.empty();//如果全部匹配，返回正确，否则是左括号多余情况，返回错误
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

5.删除字符串中的所有相邻重复项?（1047题）

题目描述：给出由小写字母组成的字符串?S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

• 输入："abbaca"
• 输出："ca"
• 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

思路：删除相邻重复项，其实就是删除对称项的问题，首先需要考虑栈能否解决，这道题首先考虑好栈如何解决的，在定义一个字符串去接收，然后要注意字符串的顺序问题，栈存放遍历过的元素，

class Solution {
public:
    void reverse(string& s,int start, int end){//自己定义的反转函数
        for(int i = start,j = end;i < j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    string removeDuplicates(string s) {//删除字符串所有相邻重复项
        stack<int>st;//定义一个栈，一般来做对称匹配问题很好用
        for(char c : s){//遍历每个字符串的字符
            if(st.empty() || c != st.top()){//如果为空或者下一个字符不等于栈顶元素压入栈中
                st.push(c);
            }else{//就是栈顶元素相等就是遇到重复元素，已经消除了一对对称的元素
                st.pop();
            }
        }
        string t = "";//定义一个字符串去接收
        while(!st.empty()){//将栈里的元素加入到字符串里
            t += st.top();
            st.pop();
        }
        reverse(t,0,t.size()-1);//因为加入字符串的顺序不对需要反转一次
        return t;
    }
};

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，

• 时间复杂度: O(n)
• 空间复杂度: O(n)

6.逆波兰表达式求值（150题）

题目描述：

根据 逆波兰表示法，求表达式的值。

有效的运算符包括?+ ,? - ,? * ,? /?。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例?1：

• 输入: ["2", "1", "+", "3", " * "]
• 输出: 9
• 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

其实相当于二叉树的后序遍历，运算符是中间节点，就是二叉树的后序遍历，这种运算有相邻字符串消除模式，想到栈的解法，

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(num2 + num1);//判断哪种运算符，对其进行操作之后压入栈中
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {//不是运算符
                st.push(stoi(tokens[i]));//stoi函数将字符串转换成整形，压入栈中
            }
        }

        int result = st.top();//结果就是最后栈顶元素
        st.pop(); //弹出
        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

7.滑动窗口最大值?（239题）

题目描述：

给定一个数组 nums，有一个大小为?k?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k?个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

思路：首先优先级队列为何不行，因为如果排序了打乱了原来顺序，错误，所以我们采用自定义的单调队列来实现，要一个压入函数，和一个弹出函数，且告知队头元素就是我们需要的最大值我们的诉求，弹出元素：如果窗口移除元素等于单调队列出口元素，弹出元素，否则不操作，Push函数，如果元素大于入口元素，则将队列入口元素弹出，改变的其实是前面的值，不改变后面的局部最大保存下来，后面就是遍历操作即可。?

class Solution {
private:
    class MyQueue{//自己实现的单调队列，其实就是维护一个所需的最大值而已
    public:
        deque<int>que;//使用deque实现单调队列，双端队列
        void pop(int value){//实现一个自己定义的弹出函数，
            if(!que.empty() && value == que.front()){//不能对空队列操作，如果要弹出的元素和队元素相等则弹出
                que.pop_front();//这部分要注意从队头移除元素
            }
        }
        void push(int value){//压入队列操作
            while(!que.empty() && value > que.back()){//不能空队列操作，我们只需要维护最大值即可，所以从队尾弹出知道小于队尾元素
                que.pop_back();
            }
            que.push_back(value);//如果小于就从队尾加入队列
        }
        int front(){//返回窗口的最大值也就是队头元素
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {//实现的函数
        MyQueue que;
        vector<int>result;//结果集
        for(int i=0;i < k;i++){//现将前k 个元素加入队列
            que.push(nums[i]);
        }
        result.push_back(que.front());//得到一个结果
        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)
• 空间复杂度: O(k)

8.前 K 个高频元素（347题）?

题目描述：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

• 输入: nums = [1,1,1,2,2,3], k = 2
• 输出: [1,2]

思路： 统计元素出现频率，对频率排序，找出前k个频率的元素，

使用数据结构map，排序使用优先级队列，

priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。?如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。

如果使用大根堆返回最小前K个元素

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

class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {//自定义一个比较规则我们要传入的哈希值形式
            return lhs.second > rhs.second;//比较的是第二个也就是数的个数
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {//实现的函数
        unordered_map<int, int> map;//定义一个哈希表map
        for (int i = 0; i < nums.size(); i++) {//对数组的每个元素进行记录个数
            map[nums[i]]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison>
            pri_que;//定义一个优先级队列小根堆排序方式
        //将哈希表遍历
        for (unordered_map<int, int>::iterator it = map.begin();
             it != map.end(); it++) {
            pri_que.push(*it);//将哈希值插入压入队列
            //固定大小为k，超过了弹出小元素
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }
        vector<int> result(k);//定义结果数据
        //因为结果需要知道前k高的元素，所以需要倒序插入到数组中
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;//插入下标
            pri_que.pop();//弹出队列
        }
        return result;
    }
};

• 时间复杂度: O(nlogk)
• 空间复杂度: O(n)

?总结：

栈与队列的理论基础：栈先进后出，队列先进先出，无迭代器，底层可以是数组链表队列，都叫容器适配器

用栈实现队列：模拟一下即可，使用两个栈，一个输出栈，一个输入栈，栈与队列不能空操作，其实就需要想明白弹出操作即可，先把输出栈清空，再把输入栈全部压入，弹出

用队列实现栈：也是模拟题，用两个队列实现，一个队列操作，另一个作为辅助队列，其实也是想明白栈的形式原理即可，计算队列的大小，把元素全部放到辅助队列，剩余就是要弹出的元素，在将辅助队列赋值给队列，一个队列也可以实现

有效括号匹配：用栈解决该问题即可，栈可以用来解决对称匹配问题，就是对对碰，考虑清楚不匹配的情况，小技巧：匹配左括号，右括号进栈，最后对比元素是否与栈顶元素相等即可，遇左进栈，遇右弹出比较即可

删除字符相邻重复项：也是消除对称的匹配项，考虑栈来求解即可，最后字符串接收一下，注意字符串的顺序，需要反转一下

逆波兰表达式：其实就是后缀表达式，要知道后缀表达式可以不用考虑运算规则，也是遇到运算符进行消除操作，遇到运算符，将两个元素弹出，做相应的运算符操作即可，再压入栈中，不是运算符需要把字符串转成整形加入栈中，最后栈顶元素就是所求

滑动窗口最大值：需要自己实现一个单调队列，要实现功能：队头元素一直是最大的，这里为何不采用优先级队列，优先级队列可能打乱原本的顺序，所以自己实现一个单调队列即可，如果遍历的元素等于队头元素就从队头弹出，如果遍历的元素大于队尾元素，需要从队尾弹出，直到小于等于队尾元素，此时我们的队头元素就是所求，其实原理就是最大值中再找接下来的局部最大值，之后就是简单的运算，先将k个数字加入，得出来一个结果，在每次弹出一个元素，加入一个元素，即可，这道题很绕，真的值得好好细品！！！！！！！！

前k个高频元素：考的知识点很多：哈希表map,优先级队列，首先需要知道优先级队列，实现大根堆和小根堆区别，此题使用小根堆，我们需要前k高频，不然大根堆是留下低频，priority_queue（需要排序的类型，vector<类型>，规则（自定义）），这里为什么使用map因为需要下标和个数，下标就是key,个数就是value，哈希表进行优先级队里排序取k个元素就是前k个高频元素，这里要注意顺序，队头才是最高频的，所以队列 实现的题都很值得多思考，真的很绕，也容易想不到！！！！！！