山东网站建设和游戏开发的公司排名,wordpress自动分享插件,网页设计的能干什么职位,手机网游传奇一、理论基础1.队列是先进先出#xff0c;栈是先进后出2.栈和队列是STL#xff08;C标准库#xff09;里面的两个数据结构。栈提供push和pop等等接口#xff0c;所有元素必须符合先进后出规则#xff0c;所以栈不提供走访功能#xff0c;也不提供迭代器。3.栈是以底层容器…一、理论基础1.队列是先进先出栈是先进后出2.栈和队列是STLC标准库里面的两个数据结构。栈提供push和pop等等接口所有元素必须符合先进后出规则所以栈不提供走访功能也不提供迭代器。3.栈是以底层容器完成所有的工作对外提供统一的接口所以STL往往不被归类为容器而被归类为container adpter容器适配器4.我们常用的SGI STL如果没有指定底层实现的话默认是以deque为缺省情况下栈的底层结构。deque是一个双向队列只要封住其中一段只开通另一端就可以实现栈的逻辑5.SGI STL中队列实现底层实现缺省情况下一样使用deque实现的std::stackint, std::vectorint third; // 使用vector为底层容器的栈
std::queueint, std::listint third; // 定义以list为底层容器的队列所以STL队列也不被归类为容器也是容器适配器二、力扣题目1、使用栈实现队列的下列操作push(x) 将一个元素放入队列的尾部pop() 从队列首部移除元素peek() 返回队列首部的元素empty() 返回队列是否为空MyQueue queue new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false说明:你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作。思路使用栈模拟队列的行为如果禁用一个栈是不行的所以需要两个栈一个输入栈一个输出栈如果进栈和出栈都为空说明模拟的队列为空了class MyQueue {
public:stackint stIn;stackint stOut;/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {// 只有当stOut为空的时候再从stIn里导入数据导入stIn全部数据if (stOut.empty()) {// 从stIn导入数据直到stIn为空while(!stIn.empty()) {stOut.push(stIn.top());stIn.pop();}}int result stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {int res this-pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res所以再添加回去return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() stOut.empty();}
};
2、用队列实现栈使用队列实现栈的下列操作push(x) 元素入栈pop() 移除栈顶元素 (没有返回值)top() 获取栈顶元素empty() 返回栈是否为空front() 返回队头元素 可以接收返回值back() 返回队尾元素思路 用两个队列que1和que2实现队列的功能que2其实完全就是一个备份的作用把que1最后面的元素以外的元素都备份到que2然后弹出最后面的元素再把其他元素从que2倒回到que1class MyStack {
public:queueint que1;queueint que2; // 辅助队列用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size que1.size();size--;while (size--) { // 将que1 导入que2但要留下最后一个元素que2.push(que1.front());que1.pop();}int result que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 que2; // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};3、有效的括号题目给定一个只包括(){}[] 的字符串判断字符串是否有效有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。思路第一种情况已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号所以return false第二种情况遍历字符串匹配的过程中发现栈里没有要匹配的字符了第三种情况遍历字符串匹配的过程中栈已经为空了没有匹配的字符了说明右括号没有找到对应的左括号return false当字符串遍历完之后栈是空的就说明全都匹配了技巧在匹配左括号的时候右括号先入栈就只需要比较当前元素和栈顶是否相等比左括号先入栈代码实现简单的多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();}
};4、删除字符串中的所有相邻重复项给出由小写字母组成的字符串S重复项删除操作会选择两个相邻且相同的字母并删除他们。在S上反复执行删除操作直到无法删除在完成所有重复项删除操作后返回最终的字符串示例输入abbaca输出ca解释例如在 abbaca 中我们可以删除 bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。思路用栈来存放遍历过的元素当遍历当前的这个元素的时候去栈里面看一下我们是不是遍历过相同数值的相邻元素如果相同则弹出元素当栈为空或者元素不相同则将此元素压入栈中最后再将栈中元素放到result字符串汇总输出class Solution {
public:string removeDuplicates(string S) {stackchar st;for (char s : S) {if (st.empty() || s ! st.top()) { //栈为空或者元素不相等st.push(s);} else {st.pop(); // s 与 st.top()相等的情况}}string result ;while (!st.empty()) { // 将栈中元素放到result字符串汇总result st.top();st.pop();//别忘了弹出栈顶的元素}reverse (result.begin(), result.end()); //因为从栈中弹出的元素是倒序的 此时字符串需要反转一下return result;}
};5、逆波兰表达式求值逆波兰表达式是一种后缀表达式所谓后缀就是指运算符写在后面平常所使用表达式是中缀表达式给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式请你计算该表达式。返回一个表示表达式值的整数。注意有效的算符为 、-、* 和 / 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。示例 1输入tokens [2,1,,3,*] 输出9 解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9特点去掉括号后表达式无歧义适合用栈操作运算遇到数字则入栈遇到运算符则取出栈顶两个数字进行运算并将结果压入栈中思路逆波兰表达式相当于二叉树中的后序遍历大家可以把运算符当作中间节点按照后序遍历左右中的顺序如果数组中元素检测到是运算符时此时要先找到需要运算的两个数字元素且这两个数字相邻且位于栈顶取出两个数字进行运算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;}
};其中stoll()函数是将字符串强制转换成long long int型6、滑动窗口最大值题目给定一个数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到滑动窗口的k个数字。滑动窗口每次只向右移动一位返回滑动窗口的最大值class Solution {
private:class MyQueue { //单调队列从大到小public:dequeint que; // 使用deque来实现单调队列// 每次弹出的时候比较当前要弹出的数值是否等于队列出口元素的数值如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() value que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值那么就将队列后端的数值弹出直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() value que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que;vectorint result;for (int i 0; i k; i) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i k; i nums.size(); i) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};
