长春新建火车站,网站做调查问卷给钱的兼职,一台服务做两个网站吗,网站模版怎么用仅做学习笔记#xff0c;详细请访问代码随想录
栈提供push 和 pop 等等接口#xff0c;所有元素必须符合先进后出规则#xff0c;所以栈不提供走访功能#xff0c;也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素
栈是以底层容器完成其所…仅做学习笔记详细请访问代码随想录
栈提供push 和 pop 等等接口所有元素必须符合先进后出规则所以栈不提供走访功能也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素
栈是以底层容器完成其所有的工作对外提供统一的接口底层容器是可插拔的也就是说我们可以控制使用哪种容器来实现栈的功能。
所以STL中栈往往不被归类为容器而被归类为container adapter容器适配器。
那么问题来了STL 中栈是用什么容器实现的
从下图中可以看出栈的内部结构栈的底层实现可以是vectordequelist 都是可以的 主要就是数组和链表的底层实现。 我们常用的SGI STL如果没有指定底层实现的话默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列只要封住一段只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现初始化语句如下
std::stackint, std::vector third; // 使用vector为底层容器的栈 队列中先进先出的数据结构同样不允许有遍历行为不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现初始化queue的语句如下
std::queueint, std::list third; // 定义以list为底层容器的队列 文档讲解 ● 20. 有效的括号
class Solution {
public:bool isValid(string s) {if (s.size() % 2 ! 0) return false; // 如果s的长度为奇数一定不符合要求stackchar 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(]);// 第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号 return false// 第二种情况遍历字符串匹配的过程中发现栈里没有我们要匹配的字符。所以return falseelse if (st.empty() || st.top() ! s[i]) return false;else st.pop(); // st.top() 与 s[i]相等栈弹出元素}// 第一种情况此时我们已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false否则就return truereturn st.empty();}
};
● 1047. 删除字符串中的所有相邻重复项
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;}
};
● 150. 逆波兰表达式求值
class Solution {
public:int evalRPN(vectorstring tokens) {// 力扣修改了后台测试数据需要用longlongstacklong long st; for (int i 0; i tokens.size(); i) {if (tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /) {long long num1 st.top();st.pop();long long 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(stoll(tokens[i]));}}int result st.top();st.pop(); // 把栈里最后一个元素弹出其实不弹出也没事return result;}
};
