【C++】容器适配器，stack，queue，priority

1. stack和queue的介绍

1.1 stack的成员函数

1.2 queue的成员函数

1.3 stack的使用

1.4 queue的使用

1.5 Container模板参数，deque

2. priority_queue优先级队列的介绍

3. stack模拟实现

3.1 初始结构

3.2 push

3.3 pop

3.4 top

3.5 empty

3.6 size

4. queue模拟实现

4.1 pop

4.2 front

4.3 back

5. priority_queue模拟实现

5.1 初始结构

5.2 push

5.3 pop

5.4 top，empty，size

5.5 仿函数

5.6 仿函数第二个用法

5.7 迭代器区间构造

6. 编程题

6.1 最小栈

6.2 栈的压入、弹出

6.3 逆波兰表达式求值

1. stack和queue的介绍

1. 模板参数有不同。

2. vector，list是自己管理数据，容器适配器是在其他容器的基础上封装实现出我要的效果。

1.1 stack的成员函数

1.2 queue的成员函数

1.3 stack的使用

void test1()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;
}

1.4 queue的使用

void test2()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;
}

1.5 Container模板参数，deque

1. 传入一个容器的模板参数，通过控制容器的行为，实现栈的效果。

2. 这就是容器适配器，你用不同的容器都能适配出栈的效果。

3. 栈和队列传入的默认容器是deque。

4. deque是双端队列，但它不是队列，因为它不要求先进先出。

5. vector不支持头插头删，list不支持随机访问，deque都支持。

6. deque擅长头尾修改。

2. priority_queue优先级队列的介绍

【接口】

【使用】

1. 不需要单独包头文件，放在queue的头文件里面。

2. 默认是大堆，top就是取堆顶的数据。

3. 插入删除是logn。

4. 降序是less，升序是greater。
void test3()
{priority_queue<int, vector<int>, greater<int>> pq;pq.push(2);pq.push(4);pq.push(7);pq.push(1);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

3. stack模拟实现

3.1 初始结构

stack类需要两个模板参数，一个是数据类型，一个是容器，成员就是容器实例化的对象。
namespace lyh
{template<typename T, typename Container = deque<T>>class stack{public:private:Container _con;};
}

3.2 push

复用容器进行尾插。
		void push(const T& val){_con.push_back(val);}

3.3 pop

复用容器进行尾删。
		void pop(){_con.pop_back();}

3.4 top

复用容器返回尾数据。
		const T& top(){_con.back();}

3.5 empty

复用容器判空。
		bool empty(){_con.empty();}

3.6 size

复用容器返回数据个数。
		size_t size(){return _con.size();}

4. queue模拟实现

4.1 pop

pop和栈不一样，pop复用容器头删。
		void pop(){_con.pop_front();}

4.2 front

复用容器返回头数据。
		const T& front(){return _con.front();}

4.3 back

复用容器返回尾数据。
		const T& back(){return _con.back();}

其他都和栈一样，因为栈在一端进出，队列在一端进一端出。

5. priority_queue模拟实现

5.1 初始结构

1. priority_queue最适合用vector。

2. 两个模板参数，一个是数据类型，一个是容器。

3. 成员是容器实例化的对象。
namespace lyh
{template<typename T, typename Container = vector<T>>class priority_queue{public:private:Container _con;};
}

5.2 push

1. 复用容器尾插数据。

2. 进行向上调整，保持数据的堆结构。

		//默认大堆//向上调整void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//插入void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}

5.3 pop

1. pop是删除堆顶的数据，先把堆顶数据和最后一个数据交换，然后复用容器尾删。

2. 换上来的数据进行向下调整保持堆的结构。

		//向下调整void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除堆顶数据void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}

5.4 top，empty，size

1. top返回第一个位置数据，empty和size复用容器即可。
		//返回堆顶数据const T& top(){return _con[0];}//判空bool empty(){return _con.empty();}//返回数据个数size_t size(){return _con.size();}

5.5 仿函数

1. 它是一个对象，但却像函数一样使用。

2. 也可以套个模板增加适配性。

3. 功能上是为了替代函数指针。

1. 给priority加多一个仿函数的模板参数。

2. 将代码中控制大堆小堆的地方(parent和child比较的代码)替换成仿函数，这样比较符号就不会写死，根据你传入的仿函数对象决定比较方式。
template<typename T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
template<typename T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};
		void adjust_up(size_t child){Compare cpr;size_t parent = (child - 1) / 2;while (child > 0){if (cpr(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}
		void adjust_down(size_t parent){Compare cpr;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && cpr(_con[child], _con[child+1])){++child;}if (cpr(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}

5.6 仿函数第二个用法

1. 如果传入了对象的指针，指针是内置类型无法重载比较运算符，单纯比较指针的话也不对，这时候就需要用仿函数定制对应的比较方法。

2. 比如，当优先级队列存的是对象的指针，那我们就写一个针对指针比较的仿函数，传入的是指针其实内部比较的还是对象。

5.7 迭代器区间构造

1. 传入一段迭代器区间，然后在初始化列表用容器去初始化。

2. 在将这段初始化的区间建堆。
		template<typename InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//建堆for (i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}

完整代码：Stack_Queue/Stack_Queue · 林宇恒/code-cpp - 码云 - 开源中国 (gitee.com)

6. 编程题

6.1 最小栈

链接：. - 力扣（LeetCode）

【思路】

1. 用两个栈实现找最小元素，一个栈正常入栈，另一个栈判断当入的值等于或小于自己才入栈。

2. 用两个栈作为类的成员变量。第一个是正常栈，第一个是标记最小元素的栈。

3. push，正常栈直接push，标记栈只有为空或者小于等于栈顶元素才push。

4. pop，先判断标记栈，如果两个栈的栈顶元素是相等的，那么两个栈都pop，如果不相等，那么只有正常栈pop。

5. top，取正常栈的栈顶元素。

6. getMin，取标记栈的栈顶元素。
class MinStack 
{
public:stack<int> st;stack<int> minst;void push(int val) {st.push(val);if(minst.empty() || val <= minst.top()){minst.push(val);}}void pop() {if(st.top() == minst.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}
};

6.2 栈的压入、弹出

链接：栈的压入、弹出序列_牛客题霸_牛客网

【思路】

1. 模拟入栈出栈。

2. 首先会提供一个入栈序列和一个出栈序列，外部循环就是根据入栈序列不断入栈，每入一个数据就下标++，全部入完循环也就结束了。

3. 每次入栈一个数据，就会进行比较，如果当前栈顶数据和出栈序列一样就出栈，然后出栈序列下标++，继续比较下一个栈顶元素，直到不匹配或栈为空。

4. 入栈，然后比较，比较完继续入栈，直到入栈结束，此时如果栈不为空，那么给的出栈序列是有问题的。
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {stack<int> st;size_t pushi = 0, popi = 0;while(pushi < pushV.size()){st.push(pushV[pushi]);++pushi;while(!st.empty() && st.top() == popV[popi]){st.pop();++popi;}}return st.empty();}

6.3 逆波兰表达式求值

链接：. - 力扣（LeetCode）

【思路】

1. 利用栈，遍历数组，

2. 如果是数字就入栈，

3. 如果是符号就出栈两个数字进行运算(要区分左右)，计算完结果要入栈，

4. 遍历完之后，栈会剩下一个值就是答案。
    bool CheckOperator(const string& s){return s == "+" || s == "-" || s == "*" || s == "/"; }int calculate(int left, const string& s, int right){if(s == "+"){return left + right;}else if(s == "-"){return left - right;}else if(s == "*"){return left * right;}else {return left / right;}}int evalRPN(vector<string>& tokens) {stack<string> st;for(int i=0; i<tokens.size(); i++){if(!CheckOperator(tokens[i])){st.push(tokens[i]);}else{int right = stoi(st.top());st.pop();int left = stoi(st.top());st.pop();int cal = calculate(left, tokens[i], right);st.push(to_string(cal));}}return stoi(st.top());}