栈和队列

特性栈 (Stack)队列 (Queue)核心原则后进先出 (LIFO, Last In First Out)先进先出 (FIFO, First In First Out)操作端只能在栈顶top一端进行操作在队尾back入队在队头front出队访问限制只能访问栈顶元素可以访问队头和队尾元素典型场景函数调用栈、括号匹配、撤销操作Undo任务调度、消息队列、广度优先搜索BFS栈 (Stack) 的操作与用法使用栈需要包含stack头文件。核心操作操作说明时间复杂度push(val)将元素val压入栈顶O(1)pop()移除栈顶元素无返回值O(1)top()返回栈顶元素的引用不删除O(1)empty()检查栈是否为空空返回trueO(1)size()返回栈中元素的个数O(1)队列 (Queue) 的操作与用法使用队列需要包含queue头文件。核心操作操作说明时间复杂度push(val)将元素val加入队尾O(1)pop()移除队头元素无返回值O(1)front()返回队头元素的引用O(1)back()返回队尾元素的引用O(1)empty()检查队列是否为空空返回trueO(1)size()返回队列中元素的个数O(1)重要注意事项pop()不返回值无论是栈的pop()还是队列的pop()都只负责移除元素不返回任何值。如果想获取并移除元素需要先调用top()/front()获取再调用pop()移除。操作前检查是否为空在调用top()、front()、back()或pop()前最好先用empty()检查容器是否为空否则可能导致未定义行为或程序崩溃。题目1用栈实现队列​​​​​​力扣题目链接注意这道题实现的函数和真实的pop是不一样的真实的pop不返回值。返回第一个数是top不是peek这是我写的第一遍代码但是是错的思路完全错误没有考虑真是使用场景应该那张纸画一画。class MyQueue { public: stackint stIn; stackint stOut; MyQueue() { } void push(int x) { stIn.push(x); } int pop() { int lstIn.size(); while(l--){ int astIn.peek(); stOut.push(a); stIn.pop(); } return stOut.peek(); stOut.pop(); } int peek() { int lstIn.size(); while(l--){ int astIn.peek(); stOut.push(a); } return stOut.peek(); } bool empty() { if(stIn.empty()stOut.empty())return true; else return false; } };然后我发现了问题标注在下面,要考虑现在stOut里有没有值如果有应该直接返回他的最上面。class MyQueue { public: stackint stIn; stackint stOut; MyQueue() { } void push(int x) { stIn.push(x); } int pop() { // 只有当stOut为空的时候再从stIn里导入数据导入stIn全部数据 if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int resultstOut.top(); stOut.pop(); return result; } int peek() { int resthis-pop();// 直接使用已有的pop函数 stOut.push(res); return res; } bool empty() { if(stIn.empty()stOut.empty())return true; else return false; } };用队列实现栈​​​​​​力扣题目链接这是我自己做出来的一个开心的表情包class MyStack { public: queueintqueue; MyStack() { } void push(int x) { queue.push(x); } int pop() { int lqueue.size()-1; while(l--){ int aqueue.front(); queue.pop(); queue.push(a); } int resqueue.front(); queue.pop(); return res; } int top() { int resthis-pop(); queue.push(res); return res; } bool empty() { return queue.empty(); } }; /** * Your MyStack object will be instantiated and called as such: * MyStack* obj new MyStack(); * obj-push(x); * int param_2 obj-pop(); * int param_3 obj-top(); * bool param_4 obj-empty(); */有效的括号力扣题目链接就是看它对不对称具体看代码简单题。class Solution { public: bool isValid(string s) { stackcharst; int ls.size(); if(l%2!0)return false; for(char a:s){ if(a()st.push()); else if(a{)st.push(}); else if(a[)st.push(]); else if(st.empty()||st.top()!a)return false; else st.pop(); } return st.empty(); } };删除字符串中的所有相邻重复项力扣题目链接依然是我自己写出来的class Solution { public: string removeDuplicates(string s) { stackcharst; for(char a:s){ if(st.empty())st.push(a); else { if(ast.top())st.pop(); else st.push(a); } } string res; while(!st.empty()){ resst.top(); st.pop(); } reverse(res.begin(),res.end());//这里记得反转一下 return res; } };逆波兰表达式求值力扣题目链接class Solution { public: int evalRPN(vectorstring tokens) { // 力扣修改了后台测试数据需要用longlong stacklong 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])); } } long long result st.top(); st.pop(); // 把栈里最后一个元素弹出其实不弹出也没事 return result; } };