栈和队列，大家应该非常熟悉，队列是先进先出，栈是先进后出。如图所示：
具体，栈与队列的实现原理等，大家可以参考我的另一篇文章【STL】stack和queue的实现原理
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
输入输出样例
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false]
题解
这是一道模拟题，用一个栈肯定是不行的，就要想办法怎么通过两个栈来实现。
代码
class MyQueue {
public:
stack stk1;
stack stk2;
MyQueue() {
}
void push(int x) {
stk1.push(x);
}
int pop() {
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
int num=stk2.top();
stk2.pop();
while(!stk2.empty()){
stk1.push(stk2.top());
stk2.pop();
}
return num;
}
int peek() {
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
int num=stk2.top();
while(!stk2.empty()){
stk1.push(stk2.top());
stk2.pop();
}
return num;
}
bool empty() {
return stk1.empty()&&stk2.empty();
}
};
225.用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
输入输出样例
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]
题解
这和上题道理是一样，想办法通过性质进行模拟。
代码
class MyStack {
public:
queue q1;
queue q2;
MyStack() {
}
void push(int x) {
q1.push(x);
}
int pop() {
int size = q1.size();
size--;
while (size--) {
q2.push(q1.front());
q1.pop();
}
int result = q1.front();
q1.pop();
q1 = q2;
while (!q2.empty()) {
q2.pop();
}
return result;
}
int top() {
return q1.back();
}
bool empty() {
return q1.empty()&&q2.empty();
}
};
20.有效的括号
题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
输入输出样例
输入：s = "()" 输出：true
题解
括号匹配是使用栈解决的经典问题。
题意其实就像我们在写代码的过程中，要求括号的顺序是一样的，有左括号，相应的位置必须要有右括号。
代码
class Solution {
public:
bool isValid(string s) { //换成switch会快一些
stack stk;
for(auto &ch:s){
if(ch=='('||ch=='['||ch=='{'){
stk.push(ch);
}else if(ch==')'){
if(!stk.empty()&&stk.top()=='('){
stk.pop();
}else{
return false;
}
}else if(ch==']'){
if(!stk.empty()&&stk.top()=='['){
stk.pop();
}else{
return false;
}
}else if(ch=='}'){
if(!stk.empty()&&stk.top()=='{'){
stk.pop();
}else{
return false;
}
}
}
if(stk.empty()) return true;
return false;
}
};
1047.删除字符串中的所有相邻重复项
题目描述
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入输出样例
输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题解
这题与上题其实是一样的，如果将每个字母看作是括号，匹配即消除，就可以转换成用栈来做。
代码
class Solution {
public:
string removeDuplicates(string s) {
stack stk;
for(auto& ch:s){
if(stk.empty()) stk.push(ch);
else if(stk.top()==ch){
stk.pop();
}else{
stk.push(ch);
}
}
string ret;
while(!stk.empty()){
ret+=stk.top();
stk.pop();
}
reverse (ret.begin(), ret.end());
return ret;
}
};
150.逆波兰表达式求值
题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
输入输出样例
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
题解
逆波兰表达式相当于是二叉树中的后序遍历。逆波兰表达式是用后续遍历的方式把二叉树序列化了。
代码
class Solution {
public:
int evalRPN(vector& tokens) {
stack stk;
for(string & s: tokens){
if(s=="+"||s=="-"||s=="*"||s=="/"){
int num1=stoi(stk.top());
stk.pop();
int num2=stoi(stk.top());
stk.pop();
int num=0;
if(s=="+") num=num2+num1;
else if(s=="-") num=num2-num1;
else if(s=="*") num=num2*num1;
else if(s=="/") num=num2/num1;
stk.push(to_string(num));
}else{
stk.push(s);
}
}
return stoi(stk.top());
}
};
239.滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
输入输出样例
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
题解
可以看作一个队列，寻找队列中最大值。但如何在队列中找到最大值？
代码
class Solution {
public:
class MyQueue { //单调队列（从大到小）
public:
deque 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();
}
};
vector maxSlidingWindow(vector& nums, int k) {
MyQueue q;
for(int i=0;i res;
res.push_back(q.front());
for(int i=k;i
347.前K个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入输出样例
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
题解
通过map进行统计数据，然后利用优先队列，得到K个出现频率最大数。
代码
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair& lhs, const pair& rhs) {
return lhs.second > rhs.second;
}
};
vector topKFrequent(vector& nums, int k) {
// 要统计元素出现频率
unordered_map map; // map
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_queue, vector>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
vector result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
