JZTXT

6 栈与队列

发布时间 2023-07-24 16:06:26作者: mobbu

栈与队列

1 栈与队列基础

  • 栈：先进后出
    img

    • 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
    • 我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

2 用栈实现队列

题目：

使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

思路：

两个栈 stkIn和stkOut

  • push():stkIn.push()
  • pop():stkIn中的元素push到stkOut中，stkOut.pop()
  • peek():利用pop，弹出后再压回到stkOut中
  • empty():stkIn和stkOut都为空则空

代码：

stack<int> stkIn;
stack<int> stkOut;
MyQueue() {

}

void push(int x) {
    stkIn.push(x);
}

int pop() {
    if(stkOut.empty()){
        while(!stkIn.empty()){
            stkOut.push(stkIn.top());
            stkIn.pop();
        }
    }
    int result = stkOut.top();
    stkOut.pop();
    return result;
}

int peek() {
    int result = this->pop();
    stkOut.push(result);
    return result;
}

bool empty() {
    return stkIn.empty()&&stkOut.empty();
}

3 队列实现栈

题目：

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

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

思路：

一个队列即可实现模拟栈

代码：

queue<int>que;
MyStack() {

}

void push(int x) {
    que.push(x);
}

int pop() {
    int size = que.size();
    while(size>1){
        que.push(que.front());
        que.pop();
        size--;
    }
    int result = que.front();
    que.pop();
    return result;
}

int top() {
    return que.back();
}

bool empty() {
    return que.empty();
}

4 有效的括号

题目：

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

有效字符串需满足：

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

思路：

定义一个栈，检测到括号就压入，遇到对应的消除，出现错误就返回无效，最后栈不为空也是无效

代码：

bool isValid(string s) {
        if (s.size() % 2 != 0) return false; 
        stack<char> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || s[i]=='{' || s[i]=='['){
                st.push(s[i]);
            }
            else if(s[i]==')' && !st.empty() && st.top()=='(') st.pop();
            else if(s[i]==']' && !st.empty() && st.top()=='[') st.pop();
            else if(s[i]=='}' && !st.empty() && st.top()=='{') st.pop();
            else return false;
        }
        if(!st.empty()) return false;
        return true;
}

5 删除字符串中的所以后相邻重复项

题目：

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

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

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

思路：

反复跟栈顶元素对比即可

这里可以把string当作栈，这样少一次颠倒的操作

代码：

string removeDuplicates(string s) {
    string result;
    for(int i=0;i<s.size();i++){
        if(result.empty() || s[i]!=result.back()){
            result.push_back(s[i]);
        }
        else{
            result.pop_back();
        }
    }
    return result;
}

6 逆波兰表达式求值

题目：

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

思路：

挨个入栈，遇到计算符，开始pop前两个元素进行计算，最后只剩一个元素就是结果

代码：

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

注意：

  • longlong定义
  • stoll:string to longlong
  • 注意是num2与num1运算

7 滑动窗口最大值

题目：

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

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

思路：

定义一个class myQueue，维护单调队列，保存窗口内的单调性，front为最大值

代码：

class Solution {
private:
    class myQueue{
    public:
        deque<int> que;
        void pop(int num){
            if(!que.empty() && num == que.front()){
                que.pop_front();
            }
        }
        void push(int num){
            while(!que.empty() && num>que.back()){
                que.pop_back();
            }
            que.push_back(num);
        }
        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++){
            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 * n),要不断在窗口内求最大值。

8 前k个高频元素

题目：

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

思路：

优先级队列priority_queue,

代码：

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<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};