前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.简介

队列多用于辅助，很少有单独的题目。例如图的BFS，需要队列辅助实现。
重点是栈的应用以及题目。—先进先出（如左右匹配）
注意：做题时，多数使用数组直接模拟栈（队列）或者直接用c++STL中的stack（queue）

二.题目

1

洛谷P4387 【深基15.习9】验证栈序列

思路：用栈模拟

按入栈顺序入栈，如果栈顶元素与出栈序列的元素相同，就将其弹出。

首先将入栈序列的第i个元素压到“stack”中，（i, j分别是入栈序列和出栈序列的下标）

判断（注意用while判断，因为可能连续弹出）“stack”中的栈顶元素是否和出栈序列中的第j个元素一致（栈为空就不用判断了）如果一致则弹出栈顶元素，j++；如果不一致则继续压入入栈序列中的第i + 1个元素。

继续判断栈顶元素是否和出栈序列中的第j个元素一致，直到i到达入栈序列的末尾。

最后如果“stack”为空或指针j到达出栈序列的末尾就输出Yes，否则输出No

#include <iostream>
#include <stack>
using namespace std;
int a[100005], b[100005];
int main() {stack<int> s;int q, n; cin >> q;while (q--) {cin >> n;while (!s.empty()) {s.pop();}for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}int j = 0;for (int i = 0; i < n; i++) {s.push(a[i]);while (s.top() == b[j]) {s.pop();j++;if (s.empty()) {break;}}}if (s.empty()) {cout << "Yes" << endl;}else {cout << "No" << endl;}}return 0;
}

2

力扣735. 小行星碰撞

思路：用栈模拟

以下情况不会发生碰撞，可把当前行星压入栈：
1.栈为空，不管当前行星是正是负(往左还是往右)都要压入栈；
2.当前行星和栈顶行星同号说明同向移动不会碰撞；
3.当前行星往右移动，栈顶行星向左移动也不会碰撞；

只有一种情况会发生碰撞，需要出栈：当前行星往左，栈顶行星往右，做判断：
1.栈顶元素大于abs(当前元素)，当前元素被撞毁；
2.栈顶元素等于abs(当前元素)，栈顶弹出和当前元素抵消；
3.栈顶元素小于abs(当前元素)，栈顶弹出，并与新栈顶继续完成上述判断；

最终返回栈即可。

class Solution {
public:vector<int> asteroidCollision(vector<int>& asteroids) {vector<int> ans;int n = asteroids.size();for(int i = 0; i < n; i++){if(ans.empty()){ans.push_back(asteroids[i]);}else {if(ans.back() < 0){ans.push_back(asteroids[i]);}else{if(asteroids[i] > 0){ans.push_back(asteroids[i]);}else{if(asteroids[i] + ans.back() > 0){continue;}else if(asteroids[i] + ans.back() == 0){ans.pop_back();}else{while(!ans.empty()&&ans.back()>0&&ans.back()+asteroids[i]<0){ans.pop_back();}if(ans.empty() || ans.back() < 0){ans.push_back(asteroids[i]);}else if(ans.back() + asteroids[i] == 0){ans.pop_back();}}}}}}return ans;}
};