C++stackqueue

目录

一、stack

1.1 简要介绍

1.2 小试身手

1.3 模拟实现

二、queue

2.1 简要介绍

2.2 小试身手

2.3 模拟实现

三、deque

3.1 简要介绍

3.2 分析底层

四、priority_queue

4.1 简要介绍

4.2 小试身手

4.3 模拟实现

五、仿函数/函数对象

5.1 简要介绍

一、stack

1.1 简要介绍

鉴于读者如果阅读到本文，应该对上述函数（empty、size、push_back等）基本用法和功能有一定了解，因此不再赘述。读者可以在queue - C++ Reference (cplusplus.com)查询详细内容

1.2 小试身手

150. 逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/参考解法：
class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for (auto& s : tokens) {if (s == "+" || s == "-" || s == "*" || s == "/") {int right = st.top();st.pop();int left = st.top();st.pop();switch(s[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;default:break;}}else {st.push(stoi(s));}}return st.top();}
};
1.3 模拟实现
#pragma once#include <vector>
//#include <deque>namespace myContainer
{    template<class T, class Container = vector<T>>    // 复用vector//template<class T, class Container = deque<T>>    // 复用dequeclass stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:Container _con;};
}
效果演示：

二、queue

2.1 简要介绍

2.2 小试身手

102. 二叉树的层序遍历https://leetcode.cn/problems/binary-tree-level-order-traversal/参考解法：


class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;int levelSize = 0;if (root){q.push(root);levelSize = 1;}vector<vector<int>> vv;while (!q.empty()){vector<int> v;while (levelSize--){TreeNode* front = q.front();q.pop();v.push_back(front->val);if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}}vv.push_back(v);// 队列中的数据个数就是下一层的数据个数levelSize = q.size();}return vv;}
};

2.3 模拟实现

#pragma once#include <deque>namespace myContainer
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}const T& front()const{return _con.front();}const T& back()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:Container _con;};
}

效果演示：

三、deque

deque -- 双队列

3.1 简要介绍

        deque结合了vector和list两者的优势并融合起来，同时必然地，deque比不过vector和list的优势区间，deque就好比一个六边形战士，杂而不精。deque的用法与vector和list几乎相同，这里不再赘述。先前我们模拟实现stack和queue的时候也都可以复用deque。

3.2 分析底层

四、priority_queue

priority_queue -- 优先级队列

4.1 简要介绍

我们可以看到，优先级队列的底层实际上是vector，但是数据的排列方式更像是堆

使用演示：

4.2 小试身手

215. 数组中的第K个最大元素https://leetcode.cn/problems/kth-largest-element-in-an-array/参考解法：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(), nums.end());while (--k)pq.pop();return pq.top();}
};

4.3 模拟实现

template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};
// class Less 和 class Greater 都是函数对象，具体知识参考后文namespace my_pq
{template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 2) / 2; i >= 0; --i){adjust_down(i);}}void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;Compare com;};
}

效果演示：

五、仿函数/函数对象

5.1 简要介绍

        仿函数实际上并不是函数，只是使用起来与函数非常相似，故称为仿函数。本质上它是一个函数对象，我们通过一段代码来了解一下

        借助模板和仿函数，我们就可以减少函数指针的使用，当然它也可以作为函数参数，为其它函数所用
void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));        这样的函数指针谁也不喜欢用
我们还可以把仿函数用在其它类中，例如上面模拟实现的 priority_queue