队列和栈

栈

1.1重排链表

  • 思路：链表大综合
  • 伪代码：
    1
    找中点，反转，合并

1.2有效的括号

  • 思路：栈
  • 伪代码：
    1
    2
    3
    4
    5
    6
    stack<char> stk;
    for 遍历字符串
      if c是左括号，栈里放右括号
      else //c是右括号
        if 栈不为空且c=堆顶元素，弹出栈顶元素    //括号匹配  else return false                     //不匹配
    return stk.empty()

1.3逆波兰表达式求值

  • 思路：
    • 后缀表达式，算符写在后面，(1+2)(3+4)=(12+)(34+)
    • 数字入栈，算符取出栈顶两个数字运算，结果入栈
  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    stack<char> stk;
    for 遍历字符串
      if 是运算符
        弹出堆顶元素
        运算
      else //是数字
        入栈
    return stk.top()

1.4用队列实现栈

  • 思路：让后入的元素到队首
    • queue1主队列，queue2入栈辅助队列
    • 后入元素进入queue2
    • queue1的元素进入queue2（后入元素到队首了）
    • queue2的元素进入queue1
  • 伪代码:

队列

2.1 最近请求次数

  • 思路：队列
  • 伪代码：
    1
    2
    3
    4
    5
    ...
      q.push(t);
      while q.front() < t-3000
        q.pop();
      return q.size;

2.2数据流中的移动平均值

  • 思路：队列
  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ...
      if q.size == maxsize{
        队首元素赋值给temp
        弹出队首元素
        和减去temp
        }
      q.push(val);
      和加上val

      return 和/size

单调栈

3.1单调栈模板

  • 思路：
  • 伪代码：
    1
    2
    3
    4
    5
    6
    for 倒着遍历输入数组nums{
      while (比较数组元素和栈顶元素)
        弹出栈中不够大的元素，也就是弹出被前面高个子遮住的矮个子
      栈顶元素赋值给输出数组res
    }
    return res;