栈：先进后出
公式：卡特兰数：n个不同的元素按照某个顺序入栈，对应的合法的出栈顺序有几个？公式如下：
C n
__2n______
n+1
题目：
给出两个序列pushed和poped两个序列，其取值从1到n(n ≤ 100000)。已知入栈序列是pushed，如果出栈序列有可能是poped，则输出Yes，否则输出No。为了防止骗分，每个测试点有多组数据，不超过5组。
输入格式
第一行一个整数q，询问次数。
接下来q个询问，对于每个询问：
- 第一行一个整数n表示序列长度；
- 第二行n个整数表示入栈序列；
- 第三行n个整数表示出栈序列；
输出格式
对于每个询问输出答案。
答案：
package 博客;
import java.util.*;
public class 栈 {
static int a[]=new int[10005];//入栈的数组
static int b[]=new int[10005];//出栈的数组
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
while(q>0){
int n=sc.nextInt();
for(int i=1;i<=n;i++){
a[i]= sc.nextInt();
}
for(int i=1;i<=n;i++){
b[i]= sc.nextInt();
}
Stack<Integer> c = new Stack<>();
int j=1;
for(int l=1;l<=n;l++)
{
c.push(a[l]);
while(!c.isEmpty() && c.peek()==b[j]){
c.pop();
j++;
}
}
if(c.isEmpty()){
System.out.println("YES");
}
else{
System.out.println("NO");
}
q--;
}
}
}
队列：一般没有单独出题，例如bfs就需要队列辅助实现
定义栈
Stack<Integer> c =newStack<>();
c.push();//出栈
c.pop();//入栈
c.peek();//确认栈顶元素，不干别的
对于队列：
LinkedList<Integer> queue =newLinkedList<>();//初始化
queue.offer();//入队
queue.poll();//出队
queue.peek();//（查看队首）