6.栈与队列

栈与队列理论基础

队列是先进先出，栈是先进后出。

1. C++中stack 是容器么？

2. 我们使用的stack是属于哪个版本的STL？

3. 我们使用的STL中stack是如何实现的？

4. stack 提供迭代器来遍历stack空间么？

5. 栈和队列是STL（C++标准库）里面的两个数据结构。

   C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。

   那么来介绍一下，三个最为普遍的STL版本：

   1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
   2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
   3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

   接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

   栈

   栈先进后出，如图所示：

   

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

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

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

   那么问题来了，STL 中栈是用什么容器实现的？

   从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

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

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

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

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

刚刚讲过栈的特性，对应的队列的情况是一样的。

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

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

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

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

计算机可以利用栈来顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的。

栈与队列套路总结

括号匹配问题

1.栈可以有效解决匹配问题。在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了

滑动窗口最大值问题

2.其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列

单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。

3.什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

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

练习

Hjk合法数学表达式提取

题目
提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回0 。
简单数学表达式只能包含以下内容：

0-9数字，符号±*
说明：
1、所有数字，计算结果都不超过long
2、如果有多个长度一样的，请返回第一个表达式的结果
3、数学表达式，必须是最长的，合法的
4、操作符不能连续出现，如 ±-+1 是不合法的

输入描述
字符串

输出描述
表达式值

用例
输入 1-2abcd
输出 -1

注意！！！本题原题描述中没有 / 除号

题解

1、找出最长合法表达式

需要遍历整个输入字符串,找出最长的合法数学表达式。

合法表达式只能包含数字和运算符 +、-、*。

使用两个指针 start 和 i 来标记当前合法表达式的起始位置和结束位置。

如果遇到非法字符,我们就需要更新 maxLen 和 result。

maxLen 记录当前找到的最长合法表达式的长度。
result 记录当前找到的最长合法表达式的计算结果。

最后,检查剩余的字符串是否构成了更长的合法表达式。

2、计算表达式的值

使用栈来计算表达式的值。

遍历表达式字符串,对于每个字符:

如果是数字,我们将其累加到 num 变量中。
如果是运算符或到达字符串末尾:
根据前一个运算符的值,将 num 压入栈或与栈顶元素进行运算。
更新当前运算符为新的运算符。
重置 num 为 0。

最后,我们从栈中弹出所有元素,并累加它们得到最终结果。

3、处理边界情况

如果输入字符串为空或不包含任何合法表达式,我们返回 0。
如果有多个长度相同的最长合法表达式,我们返回第一个出现的表达式的结果。
这种解决方案的时间复杂度为 O(n),其中 n 是输入字符串的长度。我们只需要遍历一次字符串即可找到最长合法表达式并计算其值。空间复杂度为 O(n),因为在最坏情况下,我们需要将整个字符串压入栈中。

#include <iostream>
#include <vector>
#include <stack>
#include <cctype>long getsubvalue(std::string s) {long num = 0;char sign = '+';std::stack<long> stk;for (int i = 0; i < s.size(); i ++) {char c = s[i];if (isdigit(c)) {num = num*10 + (c - '0');}if (!std::isdigit(c) && c != ' ' || i == s.size() - 1) {if (sign == '+') {stk.push(num);}else if(sign == '-') {stk.push(-num);}else if(sign == '*') {num = num * stk.top();stk.pop();stk.push(num);}sign = c;num = 0;}}long result = 0;while (!stk.empty()) {result += stk.top();stk.pop();}return result;
}long getexpressionvalue(std::string s) {int start = 0;int maxlen = 0;int len = 0;long result = 0;for (int i = 0; i < s.size(); i++) {if (i == s.size() -1 || (!std::isdigit(s[i]) && s[i] != '+' && s[i] != '-' && s[i] != '*')) {len = i - start;if (len > maxlen) {maxlen = len;result = getsubvalue(s.substr(start, len));}start = i + 1;}}return result;
}int main() {std::string s;std::getline(std::cin, s);long res = getexpressionvalue(s);std::cout << res <<std::endl;return 0;}

Hjk密码输入检测

给定用户密码输入流 input，输入流中字符 ‘<’ 表示退格，可以清除前一个输入的字符，请你编写程序，输出最终得到的密码字符，并判断密码是否满足如下的密码安全要求。

密码安全要求如下：
1、密码长度 ≥ 8；
2、密码至少需要包含 1 个大写字母；
3、密码至少需要包含 1 个小写字母；
4、密码至少需要包含 1 个数字；
5、密码至少需要包含 1 个字母和数字以外的非空白特殊字符；
注意空串退格后仍然为空串，且用户输入的字符串不包含 ‘<’ 字符和空白字符。

输入描述
用一行字符串表示输入的用户数据，输入的字符串中 ‘<’ 字符标识退格，用户输入的字符串不包含空白字符，例如：
ABC<c89%000<

输出描述
输出经过程序处理后，输出的实际密码字符串，并输出改密码字符串是否满足密码安全要求。两者间由 ‘,’ 分隔， 例如：
ABc89%00,true

解释: 多余的C和0由于退格被去除,最终用户输入的密码为ABc89%00，且满足密码安全要求输出true

示例2

输入：
ABC输出：
ABC,false解释: 不满足密码安全要求

解题思路
处理退格符号 ‘<’，使用栈遍历输入字符串，遇到字符 ‘<’ 时将栈顶元素出栈，表示退格操作，否则将当前字符压入栈中。然后构建密码字符串，遍历完输入字符串后，栈中剩下的字符就是最终的密码字符，因为退格符号会将前一个输入字符删除。再检查密码安全性，遍历密码字符串，判断是否满足以下条件：
长度 ≥ 8
至少包含一个大写字母
至少包含一个小写字母
至少包含一个数字
至少包含一个字母和数字以外的非空白特殊字符
————————————————

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
#include <cctype>std::string& getreal(std::string& s) {std::stack<int> stk;for (int i = 0; i < s.size(); i ++) {if (s[i] == '<' && !stk.empty()) {stk.pop();}else {stk.push(s[i]);}}std::string temp;while (!stk.empty()) {char c = stk.top();temp.push_back(c);stk.pop();}std::reverse(temp.begin(), temp.end());return temp;
}bool istruepass(std::string& s) {bool hasupper = false;bool haslowwer = false;bool hasnum = false;bool hasother = false;for (char c: s) {if (std::isdigit(c)) hasnum = true;else if (std::isupper(c)) hasupper = true;else if (std::islower(c)) haslowwer = true;else hasother = true;}if (s.size() >= 8 && haslowwer && hasnum && hasupper) {return true;}else return false;
}int main() {std::string s;std::getline(std::cin, s);std::string realinput = getreal(s);bool res = istruepass(realinput);std::string out = res?"true":"false";std::cout << realinput << "," << out << std::endl;return 0;
}

Hjk插队

银行有客户，每个客户都有一个优先级，从1到5，其中1级最高、5级最低。假如你在银行办事，那高优先级的客户可以随时走到你前面。现在，给你一串事件，描述了哪些客户什么时候到，以及什么时候有客户办事。每当有客户办事，你要告诉我们是哪位客户。如果几位客户优先级一样，那就是先到先办。

输入格式：

第一行是一个正整数 n，告诉你有多少事件。(1 ≤ n ≤ 500)
接下来的 n 行描述事件：
如果是 “a” 开头，代表有客户到。然后会跟着两个数字：客户编号和优先级。
如果是 “p”，那么代表现在轮到优先级最高的客户办事。
输出格式：

对于每个 “p” 事件，输出办事的客户编号。
示例：

输入：

4
a 1 3
a 2 2
a 3 2
p

输出：

2

题解

使用优先队列（在C++中是priority_queue），以保持客户按照优先级和到达顺序进行排序。优先级最高的（数值最小）客户将排在队列的前面，如果优先级相同，则比较他们到达的顺序，先到达的客户将排在前面。

    #include <iostream>#include <queue>struct Comsumer {int id;int priority;int order;Comsumer(int x, int y, int z):id(x), priority(y), order(z) {}};struct Compare {bool operator()(const Comsumer& a, const Comsumer& b) {if (a.priority == b.priority) return a.order > b.order;else return a.priority > b.priority;}};int main() {int n;std::cin >> n;std::priority_queue<Comsumer, std::vector<Comsumer>, Compare> pq; //放在循环外int order = 1;for (int i = 0; i < n; i++) {char t;int id;int priority;std::cin >> t ;if (t == 'a') {std::cin >> id >> priority;//存入优先队列pq.push(Comsumer(id, priority, order));order ++;}else if (t == 'p') {if (!pq.empty()) {int res = pq.top().id;pq.pop();std::cout << res << std::endl;}}}return 0;}