算法讲解15：栈

栈：先进后出

公式：卡特兰数：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();//（查看队首）