用数组模拟栈 队列 以及单调栈 单调队列应用

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh  tt)
{

}

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i  )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

#includeusing namespace std;
const int N=100010;
int stk[N],n,tt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x) tt--;
        if(tt)
        {
            cout" ";
        }
        else
        {
            cout"-1"" ";
        }
        stk[++tt]=x;
    }
}

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i  )
{
    while (hh // 判断队头是否滑出窗口
    while (hh  ;
    q[ ++ tt] = i;
}

#includeusing namespace std;
const int N=1000010;
int a[N],q[N];
int main()
{

    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i)
        scanf("%d",&a[i]);
    int hh=0,tt=-1;
    for(int i=0;i)
    {
        if(hh1>q[hh]) hh++;
        while(hh=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    printf("\n");
      hh = 0, tt = -1;
   for(int i=0;i)
    {
        if(hh1>q[hh]) hh++;
        while(hh;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
     printf("\n");

    return 0;
}