html网站模版,邯郸网站建设网站开发,做网站有哪些按钮,品牌设计包括哪些1、leecode232 用栈实现队列
使用栈模拟队列的行为#xff0c;仅使用一个栈是不行的#xff0c;所以需要两个栈#xff0c;一个是输入栈#xff0c;一个是输出栈。
#includeiostream
#includevector
#includestring
#includestack
#incl…1、leecode232 用栈实现队列
使用栈模拟队列的行为仅使用一个栈是不行的所以需要两个栈一个是输入栈一个是输出栈。
#includeiostream
#includevector
#includestring
#includestack
#includequeue
using namespace std;class MyQueue {private:stackint stack_in;stackint stack_out;public:void push(int value) {stack_in.push(value);}int pop() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result stack_out.top();stack_out.pop();return result;}int top() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result stack_out.top();return result;}bool empty() {return stack_in.empty() stack_out.empty();}
};void main() {MyQueue queue;queue.push(1);queue.push(2);queue.push(3);cout the first value: queue.pop() endl;cout the next value: queue.pop() endl;cout the next value: queue.pop() endl;cout hello world endl;
}2、用队列实现栈。 leetcode225
队列的规则是先进先出把一个队列中的数据导入另一个队列数据的顺序并没有变。所以用栈实现队列和用队列实现栈的思路是不一样的取决于这两个数据结构的性质。如果用两个对列实现栈那么两个队列就没有输入队列和输出队列的关系另一个队列完全是用来备份的。
#includeiostream
#includevector
#includestring
#includestack
#includequeue
using namespace std;class MyStack {private:queueint queue_fir;queueint queue_sec;public:void push(int val) {queue_fir.push(val);}int pop() {int size queue_fir.size();size--;while (size--) {queue_sec.push(queue_fir.front());queue_fir.pop();}int result queue_fir.front();queue_fir.pop();queue_fir queue_sec;while (!queue_sec.empty()) {queue_sec.pop();}return result;}int top() {return queue_fir.back();}bool empty() {return queue_fir.empty();}
};void main() {MyStack stack;stack.push(1);stack.push(2);stack.push(3);cout stack.pop() endl;cout stack.pop() endl;cout stack.pop() endl;cout hello world endl;
}3、匹配括号 leetcode20
这里有三种不匹配的情况
1、第一种情况字符串中左方向的括号多余了所以不匹配。
第一种情况已经遍历了字符串但是栈不为空说明有相应的左括号但没有右括号所以返回错误。
2、第二种情况括号没有多余但是括号的类型不匹配。
在遍历字符串的过程中发现栈中没有要匹配的字符返回错误。
3、第三种情况字符串中右方向的括号多余了所以不匹配。
在遍历字符串的过程中栈已经为空没有匹配的字符了说明右括号没有找到对应的左括号返回错误。
那么什么时候说明左括号和右括号全部匹配了呢如果遍历字符串之后栈是空的则说明全都匹配了。
#includeiostream
#includevector
#includestring
#includestack
#includequeue
using namespace std;class Solution {private:stackint st;public:bool IsValid(string s) {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(]);}else if (st.empty() || st.top() ! s[i]) {return false;}else {st.pop();}}return st.empty();}
};void main() {string s (){}[]{[]};Solution slo;slo.IsValid(s);cout hello world endl;
}4、滑动窗口最大值 leetcode239
一个大小为k的滑动窗口从前向后在数组nums上移动返回滑动窗口每移动一次时窗口中的最大值。
1、设计单调对列设计的时候pop和push操作保持如下规则
pop()如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不进行任何操作。
push()如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于或等于队列入口元素的数值。
基于以上规则每次窗口移动的时候只要调用que.front()就可以返回当前窗口的最大值。
#includeiostream
#includevector
#includestring
#includestack
#includequeue
#includedeque
using namespace std;//单调队列从大到小
class MyQueue {private:dequeint que;//使用deque实现单调队列public://每次弹出元素时比较当前要弹出元素的数值是否等于队列出口元素的数值如果相等则弹出。//弹出元素之前需要判断队列当前是否为空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);}int front() {return que.front();}
};void main() {cout hello world endl;
}这样就用deque实现了一个单调队列接下来解决求滑动窗口最大值的问题就简单了。
#includeiostream
#includevector
#includestring
#includestack
#includequeue
#includedeque
using namespace std;class Slotuion {private://单调队列从大到小class MyQueue {private:dequeint que;//使用deque实现单调队列public://每次弹出元素时比较当前要弹出元素的数值是否等于队列出口元素的数值如果相等则弹出。//弹出元素之前需要判断队列当前是否为空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);}int front() {return que.front();}};private:MyQueue que;public:vectorint MaxSlidingWindow(vectorint input,int k) {vectorint result;for (int i 0; i k; i) {que.push(input[i]);}result.push_back(que.front());for (int i k; i input.size(); i) {que.push(input[i]);que.pop(input[i - k]);result.push_back(que.front());}return result;}
};void main() {vectorint input { 2,4,-2,-4,3,1,5 };int k 4;Slotuion slo;slo.MaxSlidingWindow(input, k);cout hello world endl;
}
