代码随想录第七章 栈与队列

1、leecode232 用栈实现队列

使用栈模拟队列的行为，仅使用一个栈是不行的，所以需要两个栈，一个是输入栈，一个是输出栈。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;

class MyQueue {
 private:
	stack<int> stack_in;
	stack<int> 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

队列的规则是先进先出，把一个队列中的数据导入另一个队列，数据的顺序并没有变。所以用栈实现队列和用队列实现栈的思路是不一样的，取决于这两个数据结构的性质。如果用两个对列实现栈，那么两个队列就没有输入队列和输出队列的关系，另一个队列完全是用来备份的。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;

class MyStack {
 private:
	queue<int> queue_fir;
	queue<int> 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）、第三种情况，字符串中右方向的括号多余了，所以不匹配。

在遍历字符串的过程中栈已经为空，没有匹配的字符了，说明右括号没有找到对应的左括号，返回错误。

那么什么时候说明左括号和右括号全部匹配了呢？如果遍历字符串之后，栈是空的，则说明全都匹配了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;

class Solution {
 private:
	stack<int> 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()就可以返回当前窗口的最大值。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;

//单调队列，从大到小
class MyQueue {
 private:
	deque<int> 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实现了一个单调队列，接下来解决求滑动窗口最大值的问题就简单了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;

class Slotuion {
 private:
	//单调队列，从大到小
	class MyQueue {
	 private:
		deque<int> 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:
	vector<int> MaxSlidingWindow(vector<int> &input,int k) {
		vector<int> 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() {
	vector<int> input = { 2,4,-2,-4,3,1,5 };
	int k = 4;
	Slotuion slo;
	slo.MaxSlidingWindow(input, k);
	cout << "hello world" << endl;
}

5、前K个高频元素 leetcode347

在一个数组中找到出现频率前k高的元素。

这道题目主要涉及如下三个部分：

(1)、统计元素出现的次数；

(2)、对次数进行排序；

(3)、找出前k个高频元素。

首先统计元素出现的次数，可以使用map进行统计。然后对次数进行排序，这里可以使用一种容器适配器即优先级对列。

优先级队列是一个拥有权值的queue，其内部元素按照元素的权值排列。权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性，表现为一个vector表现的完全二叉树。

1、优先级队列介绍

这是一个queue，所以只允许在底端加入元素，并从顶端取出元素。
但是优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。
缺省的情况下维护的是一个大堆，即权值以从高到低排列。

其中Type代表数据类型，Container代表容器类型，缺省状态为vector; Functional是比较方式，默认采用的是大顶堆(less<>)。

#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_map>
using namespace std;



class Solution {
 public:
	class MyCompare {
	 public:
		bool operator()(const pair<int,int>& lhs, const pair<int, int>& rhs) {
			return lhs.second > rhs.second;
		}
	};
	vector<int> TopKFrequent(vector<int>& input, int k) {
		unordered_map<int, int> map;
		for (int i = 0; i < input.size(); i++) {
			map[input[i]]++;
		}
		priority_queue<pair<int,int>,vector<pair<int,int>>, MyCompare> pri_que;
		for (auto iter = map.begin(); iter != map.end(); iter++) {
			pri_que.push(*iter);
			if (pri_que.size() > k) {
				pri_que.pop();
			}
		}
		vector<int>result(k);
		for (int i = k - 1; i >= 0; i--) {
			result[i] = pri_que.top().first;
			pri_que.pop();
		}
		return result;
	}
	
};



void main() {
	vector<int> input = { 2,2,2,2,2,3,3,3,1 };
	int k = 2;
	Solution slo;
	slo.TopKFrequent(input, k);
	
	cout << "hello world" << endl;
}

5、接雨水 leetcode42

给出一排宽度为1，高度为n的柱子，求可以接到雨水的面积。

输入：height=[1,0,2,1,3,1,0,1,2,0,1]。输出为7.

（1）、双指针解法

从头遍历所有的列，注意第一个柱子和最后一个柱子不接雨水，整体代码如下。

#include<iostream>
#include<vector>

using namespace std;

//双指针算法
class Solution {
 public:
	 int Trap(vector<int>& height) {
		 int sum = 0;
		 for (int i = 0; i < height.size(); i++) {
			 if (i == 0 || i == height.size() - 1) {
				 continue;
			 }
			 int rheight = height[i];
			 int lheight = height[i];
			 // 找到右边那个最大的柱子
			 for (int r = i + 1; r < height.size(); r++) {
				 if (height[r] > rheight) {
					 rheight = height[r];
				 }
			 }
			 //找到左边最大的柱子
			 for (int l = i - 1; l >= 0; l--) {
				 if (height[l] > lheight) {
					 lheight = height[l];
				 }
			 }
			 int h = min(rheight, lheight) - height[i];
			 if (h > 0) {
				 sum = sum + h;
			 }
		 }
		 return sum;
	}
};

void main() {
	vector<int> height = { 1,0,2,1,3,1,0,1,2,0,1 };
	Solution slo;
	slo.Trap(height);
	cout << "hello world" << endl;
}