字数统计: 2.4k字   |   阅读时长: 10分

栈与队列

栈先进后出, 队列先进先出

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

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

也可以指定list 为起底层实现，初始化queue的语句如下：

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

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MyQueue {
public:
    stack <int> stIn;
    stack <int> stOut;
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty())  //只有stOut为空时才将stIn的元素push进stOut中, 否则直接将stOut的top值pop出
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result; //返回删除掉的top()元素
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

/**
 * 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();
 */

思路就是用两个栈模拟一个队列。

225. 用队列实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyStack {
public:
    queue <int> que;

    MyStack() {
        
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        size = size - 1;
        while(size--)
        {
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

/**
 * 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();
 */

单队列实现栈,思路就是每次只pop出队列尾的元素，其余元素依次添加到队列的末尾

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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() || st.top() != s[i]) //对应第三个和第二个动图 
            return false;
            else
            st.pop();
        }
        return st.empty(); //对应第一个动图
    }
};

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S)
        {
            if(result.empty() || result.back() != s)
            result.push_back(s);
            else
            result.pop_back();
        }
        return result;
    }
};

注意字符串的操作, s.back()是判断字符串尾部元素。 push_back(s)是将s放在字符串的末尾, pop_back(s)是将s放在字符串的开头。

150. 逆波兰表达式求值

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

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

说明：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]));
        }
        int result = st.top();
        return result;
    }
};

注意C++中单引号和双引号之间的区别, 单引号是字符型， 双引号是字符串型.单引号引起的一个字符实际上代表一个整数。双引号引起的字符串，代表的却是一个指向无名数组起始字符的指针。该数组会被双引号之间的字符以及一个额外的二进制为零的字符 ‘\0’ 初始化。

实际上 ”a” 是 “a\0”，以’\0’结尾。而‘a’单单表示a这个字符。
字符串可以是”abcde”这样的表示多个字符的一个组合，但是’abcde’这样就是错误的！！！

大顶堆和小顶堆
大顶堆：二叉树每个结点的值都大于或等于其左右孩子结点的值

小顶堆：二叉树每个结点的值都小于或等于其左右孩子结点的值

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//单调队列的思想, 始终保持队列的front对应的是滑动窗口内的最大值
class Solution {
private:
    class MyQueue{
        public:
        deque <int> que;
        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++)
        {
            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;
    }

};

本题用到了deque双向队列, 有push_front, pop_front, push_back, pop_back等接口

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { //重写仿函数
            return lhs.second > rhs.second;
        }
    };
        unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++)
        {
            map[nums[i]]++;
        }
        //利用优先队列对元素出现的频次进行排序
        priority_queue <pair<int,int>, vector<pair<int,int>>,mycomparison> pri_que; //构建最小堆
        //priority_queue <pair<int,int>> pri_que; 
        for(unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++)
        {
            pri_que.push(*it);
            if(pri_que.size() > k)
            pri_que.pop();
        }
        vector <int> result(k);
        for(int i = k - 1; i >= 0; i--)
        {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result; 
    }
};

思路: 用unordered_map进行字符频率统计, 然后用优先队列对前k个高频字符进行统计, 最后输出前k个高频字符。 最小堆作用是找到n个最大的元素, 每次插入元素只需要与根节点进行对比即可, 也就是比较当前元素和此前n个元素中最小的, 这样就能得到n个最大的元素, 最后返回top时从树的根节点开始, 一直到最大的元素, 因此最后如果想按从大到小的顺序输出, 就要逆序输出。

补充: 除了重写仿函数之外, 还可以用运算符重载的方法进行比较, 代码如下:

1
2
3
4
5
6
7
8
9
10
//方法1
struct tmp1 //运算符重载<
{
     int x;
     tmp1(int a) {x = a;}
     bool operator<(const tmp1& a) const
     {
         return x < a.x; //大顶堆
     }
 };

优先队列首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

基础知识补充
STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。其中，各适配器所使用的默认基础容器以及可供用户选择的基础容器，如表 1 所示。

deque在内存中的分布是不连续的, deque是双端队列。

stack不允许有遍历行为, 不提供走访功能，也不提供迭代器。

queue 所有元素的进出都必须符合 “先进先出” 的条件，只有 queue 顶端的元素，才有机会被外界使用。 queue 不提供遍历功能，也不提供迭代器。

而关联容器(查找表)包括set、map、hash_set、hash_map，主要用于查找，提供迭代器

  • vector函数: push_back、pop_back、back、front、按下标取值[]
  • list函数: push_back、pop_back、push_front、pop_front、back、front
  • deque函数: push_back、pop_back、push_front、pop_front、back、front、按下标取值[]
  • stack函数: push、pop、top
  • queue函数: push、pop、back、front
  • priority_queue函数: push、pop、top
  • //vector底层数据结构为数组,不提供前端插入、删除函数，开销太大
  • //list底层数据结构为链表，不提供按下标取值[]函数，开销太大

71. 简化路径

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊