栈

首先是先进后出的数据结构

https://download.tooc.xlj0.com/uploads/179/%E7%AE%97%E6%B3%95/Pasted%20image%2020231018220744.png

STL中栈的一些函数

//元素访问
st.top()//返回栈顶

//修改
st.push()//传入参数到栈顶
st.pop()//弹出栈顶

//容量
st.empty()//返回是否为空
st.size()//返回元素数量

来一道模板题

现在有n部火车，每一部火车都有一个1∼n的编号且各不相同（火车编号构成一个
排列）。现在他们按照给定的顺序排列在一条轨道上，且可以向两个方向移动，问他们
否通过一个车站，且每部火车至多进站一次，使得出站口的编号顺序变为升序？
车站是一个栈结构，位于输入队列的轨道中间，构成一个T字形，初始时火车都在车站
右侧。
如果可以输出”Yes”，如果不行输出”No”。（不带引号）

分析：就是将最后结果的排序是必须是升序的，就比如是进站的顺序是312，但是出栈的情况是123。在这里就是用栈的情况，将不符合的先存起来然后符合情况后在出栈

//输入案例
//3
//3 1 2

//输出结果
//Yes
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

  

const int N = 1e5 + 9;

  

int a[N], pos;

  

void solve() {

  int n;

  cin >> n;

  for (int i = 1; i <= n; ++i) cin >> a[i];

  

  stack<int> stk;

  pos = 1;

// i表示左边轨道所需的列车编号

  for (int i = 1; i <= n; ++i) {

//如果不是所需的（想要的），就一直找

  while (pos <= n && (stk.empty() || stk.top() != i)) stk.push(a[pos++]);
//就是在pos还是小于n的情况下，并且还没有进栈，并且栈的顶部是没有与i对应的，那么就进栈
  

  if (stk.top() == i)//如果对应就移除

    stk.pop();

  else {//就是整个while循环完了还是没有能出栈的，说明就是没有升序的情况

    cout << "No" << '\n';

     return;

    }

  }

cout << "Yes" << '\n';

}

  

int main() {

  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int _ = 1;

  while (_--) solve();

  return 0;
}