数组模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Stack {
	final int N = 10010;
    int[] stk = new int[N];
    int tt;
    
    //插入
    stk[++tt] = x;
    
    //弹出
    tt --;
    
    //判断栈是否为空
    if (tt > 0) notempty;
    else isempty;
    
    //栈顶
    stk[tt];
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

1
2
3
4
5
int tt = 0;
for (int i = 0; i <= n; i++) {
	while (tt && check(stk[tt], i)) tt--;
	stk[++tt] = i;
}

数组模拟队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Queue {
	final int N = 10010;
    int[] q = new int[N];
    int tt = -1, hh;
    
    //插入
    q[++tt] = x;
    
    //弹出
    hh ++;
    
    //判断队列是否为空
    if (hh <= tt) notempty;
    else isempty;
    
    //取出队头元素
    q[hh];
}

单调队列

常见模型：找出滑动窗口中的最大值/最小值

1
2
3
4
5
6
7
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}