线性表

• 每个线性表上的数据最多只有前和后两个方向，如 数组、链表、队列、栈 等
• 非线性表，数据之间不是简单的前后关系，如 二叉树、堆、图 等

栈 Stack

“栈”数据结构的特点

1. 后进者先出，先进者后出（类似一堆盘子）
2. 是一种“操作受限”的线性表（只有 入栈 push、出栈 pop 的操作）

栈的实现，空间复杂度 O（1）

1. 顺序栈，用数组实现的栈
   • 出栈操作，时间复杂度 O（1）
   • 入栈操作，最好情况时间复杂度O（1），最差情况时间复杂度 O（n），均摊时间复杂度 O（1）
2. 链式栈，用链表实现的栈
   • 出栈、入栈操作，时间复杂度 O（1）

栈的实际应用

• 函数调用栈
  1. 操作系统给每个线程分配一块独立的内存空间，以栈的结构来存储函数调用时的临时变量
  2. 每进入一个函数，将临时变量作为一个栈帧入栈，当被调用函数执行完成后，将这个函数对应的栈帧出栈
• 表达式求值
  1. 使用两个栈来分别保存，操作数和运算符
  2. 从左向右遍历表达式，当遇到数字时，直接压入操作数栈，遇到运算符时，与运算符的栈顶元素进行比较
  3. 当运算符栈顶的运算符优先级高时，将当前运算符压入栈，当运算符栈顶的运算符优先级低或相同时，从运算符栈中取栈顶运算符，从操作数栈的栈顶取两个操作数，进行计算，并将计算后的结果压入操作数栈
  4. 持续比较，直到结束
• 检验括号匹配
  1. 从左到右依次扫描字符串，用栈保存未匹配的括号（如，( [ { 等）
  2. 当扫描到需要匹配的括号（如，) ] } 等），则从栈顶取出一个括号，若匹配，则继续，若不匹配，则说明为非法格式
  3. 当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式，否则，说明有未匹配的括号，则为非法格式
• 浏览器的前进后退功能
  1. 使用两个栈 X Y
     • 把首次浏览的页面一次压入栈 X
     • 点击后退时，依次从栈 X 中出栈，并将出栈的数据放入栈 Y，若栈 X 为空，则说明无法后退
     • 点击前进时，依次从栈 Y 中出栈，并将出栈的数据放入栈 X，若栈 Y 为空，则说明无法前进
     • 当跳转到新的页面时，则需要清空栈 Y
  2. 使用双向链表，使用 prev 和 next 来跳转

内存中的堆栈

1. 内存中的堆栈和数据结构中的堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构
2. 内存空间在逻辑上分为三部分：代码区，数据静态区和动态数据区，动态数据区分为 栈区 和 堆区
3. 代码区：存储方法体的二进制代码，高级调度（作业调度），中级调度（内存调度），低级调度（进程调度）控制代码区执行代码的切换
4. 静态数据区：存储全局变量、静态变量、常量，常量包括 final 修饰的常量和 String 常量，系统自动分配和回收
5. 栈区：存储运行方法的形参、局部变量、返回值，由系统自动分配和回收
6. 堆区：new 一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据

堆和栈的区别和联系

1. 堆和栈都是指内存空间，不同的是，堆是按需申请、动态分配，并且需要手动释放。栈是由系统自动分配，自动释放，当申请内存超过可用内存时，将报异常提示栈溢出
2. 栈的内存空间是连续的，堆的内存空间则不是。当收到申请空间的请求时，遍历操作系统中记录空闲内存地址的链表，寻找第一个空间大于所申请空间的堆结点，并将此结点从空闲结点链表中删除

队列 Queue

“队列”数据结构的特点

1. 先进者先出（类似于排队）
2. 是一种“操作受限”的线性表（只有 入队 enqueue、出队 dequeue 操作）

队列的实现

• 顺序队列，用数组实现的队列
  1. 有两个指针，分别指向 队列头、队列尾
  2. 入队操作，时间复杂度 O（1）
     • 由于数组的特性，当队列需要调整长度时，需要数据搬移操作
  3. 出队操作，均摊复杂度 O（1）
     • 每次出队，需要删除数组的第一个元素，若仍旧需要使队列头指向数组的第一个元素，则需要数据搬移，时间复杂度为 O（n）
     • 优化：在队列无空闲空间时，触发一次数据的搬移操作
• 链式队列，用链表实现的队列
  1. 有两个指针，分别指向队列头、队列尾
  2. 入队操作，时间复杂度 O（1）
     • 由于链表的特性，可以实现长度无限的队列
  3. 出队操作，时间复杂度 O（1）
• 循环队列，队列头、队列尾相连结的队列，一般用数组实现
  • 双指针
    1. 有两个指针，分别指向队列头、队列尾
    2. 入队操作，时间复杂度 O（1）
       • 避免了顺序队列的数据搬移工作，循环入队
    3. 出队操作，时间复杂度 O（1）
    4. 注意事项
       • 确定好队空和队满的判定条件，队空 head == tail、队满 （tail + 1）% n = head （head + tail + 1 = n）
       • 循坏时，头尾指针的位置要取模
  • 头指针 + 队列长度
    1. 入队操作，时间复杂度O（1）
    2. 出队操纵，时间复杂度O（1）
    3. 注意事项
       • 确定好队空和队满的判定条件，队空 count == head、队满 count == limit
       • 循环时，头指针的位置要取模，head = ( head + 1 ) % limit，尾指针，tail = ( head + count ) % limit
• 双端循环队列，可以分别从队列头、队列尾执行出队、入队操作
  1. 在队列中预留一个位置，使用两个指针，分别指向队列头、队列尾的下一个位置
  2. 注意事项：
     • 确定好队空和队满的判定条件，队空 head == tail、队满 ( tail + 1 ) % limit == head
     • 循环时，头尾指针的位置要取模，head = ( head + limit - 1 ) % limit，tail = ( tail + 1 ) % limit
     • 头指针先取模，再赋值，尾指针先赋值，再取模
• 阻塞队列
  1. 在队列的基础上增加阻塞操作
  2. 在队列为空时，从队列头取数据会被阻塞，在队列满时，入队操作被阻塞
  3. 生产者 - 消费者模型
• 并发队列
  1. 线程安全的队列，同一时刻仅允许一个入队或出队操作
  2. 可以使用基于数组的循环队列，利用 CAS 原子操作
     • 入队操作，比较入队前和入队时的 tail，若无变化，则允许入队
     • 出队操作，比较出队前和出队时的 head，若无变化，则允许出队