栈与队列

模拟栈与队列

  int stk[N], tt;  //tt为栈顶
  
  stk[++ tt] = x;  //入栈
  
  tt --;  //弹出
  
  if(tt > 0)  not empty;
  else empty;
  
  
  //----------
  
  //队列
  //先入先出
  
  int q[N], tt, hh;  //队尾与队头
  
  //入队
  q[++ tt] = x;
  
  //出队
  hh ++;    //hh本为0，向tt靠近
  
  if(hh <= tt)  not empty;
  else empty;

单调

考虑暴力情况，再试着剪枝，删掉一些冗余的元素，看剩下的元素是否满足某些性质，如果单调，则可以用单调栈或单调队列做

单调栈

• 使用时关键在于解决找到一个数的左边或右边，第一个与它满足某种条件的数（如小于或大于）
• 将该数在给定数组位置之前的所有数入栈（暴力来看其实就是对一个数，在其前面（或后面）的所有数里找到第一个满足条件的数，这样就相当于维护了一个栈，将所有的数入栈）入栈前明确条件，若要找到小于的，就应当把之前数组中大于后者的去掉，因为后者更优，离得更近且更小，能用后者肯定不会用到前者（找到特性简化栈）， 再入栈找到满足条件的第一个数。

单调队列

• 同理于单调栈
• 用于处理如一给定数组中滑动窗口，满足在队尾进队，队头出队的形式，求某一要求值
• 去除队伍中不会再用到的值简化队列，如要求最小值，但入队有小值时，队头的值不止寿命短而且大则可以去掉，此时队列变成单调，头小尾大