栈和队列学习笔记（C#）

线性表：栈、队列                     抽象的数据结构

栈：操作受限的线性表，只允许一段插入或删除，功能上可替代，操作上越灵活使用时就不可控，先进后出、先出后进

    入栈和出栈都在栈顶插入或删除数据

    数组实现的栈：顺序栈

    链表实现的栈：链式栈

入栈的最好情况时间复杂度O（1），最坏O（n），平均=最坏

摊还分析法=最好

只有在个别时候退化为O（n），均摊到其他的操作上。

函数调用栈：存储函数调用时的临时变量

编译器实现表达式求值

    用到两个栈：操作数（红色）、运算符（黄色）

浏览器的前进和后退（a、b、c三个网页，三次后退和前进）

队列

    先进先出

    入队（数据放在队尾）、出队（队头取出数据）

    顺序队列：数组实现

    链式队列：链表实现

    

当满了以后搬一次数据O（1）

环形队列操作

队满的判断条件tail==n

队空的判断条件tail==head

队满（tail+1）%n=head

阻塞队列

    生产-消费者模型：生产数据的速度过快，消费者来不及消费，很快就会满。生产者和消费者个数，N个消费者对应一个生产者。

循环队列比链表（没有随机访问特性）应用更广泛

并发队列（特殊特性的队列应用广泛）

线程池中应用

    处理速度和线程个数不是线程正相关

    过多的线程反而会导致CPU频繁切换

    固定大小的线程池，没有空间处理策略：

        非阻塞的处理方式，直接拒绝（微服务里的熔断）

    阻塞的处理方式，排队、等空闲线程

    先进先服务，存储排队请求。

    无限排队的无界队列，请求处理时间长，对响应敏感不合适（链式队列）

    有界队列，Polly瞬态故障，限制并发数（12个并发，10个排队）直接拒绝。    

队列可以应用在任何有限资源池，数据库连接池。