1. 栈
1.1 概念
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算, 即顶端(top), 另一端称之为低端(bottom)
栈中的元素离底端越近, 代表其在栈中的时间越长, 因此栈的底端是具有非常重要的意义的.最新添加的元素会被最先移除. 这种排序原则被称作LIFO(last-in fist-out), 即先进后出(后进先出). 它提供了一种基于在集合中的时间来排序的方式.
在现实生活中, 手枪弹夹就是典型的栈模型.
1.2 相关方法
- Stack() 创建空栈并返回
- push(item) 压栈, 将一个元素添加到栈顶, 就地修改,无返回值
- pop() 弹栈, 将栈顶元素弹出, 返回被弹的元素
- peek() 访问并返回栈顶元素
- isEmpty 检察栈是否为空 bool类型
- size() 返回栈的长度 int类型
1.3 栈实现
栈遵循先进后出原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加或删除元素，因此栈可以视为一种受限制的数组或链表。
1.3.1 基于数组的实现
用数组构建栈时，数组开头为栈底, 数组结尾为栈顶的实现方式要比数组开头为栈顶, 结尾为栈底的方式效率显然是要高的.
1.3.2 基于链表实现
使用链表实现栈时，大样将链表的头节点视为栈顶，尾结点视为栈底。对于入栈操作，只需要将元素插入链表头部，这种节点插入方法被称为“头插法”，而对于弹栈操作，只需要将头节点从链表中删除即可。
1.3.3 两种实现对比
支持操作：
- 两种实现都支持栈定义中的各种操作
时间效率：
- 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
- 基于链表实现的栈可以提供更加稳定的效率表现。
空间效率:
- 基于数组实现的栈可能造成一定的空间浪费
- 在初始化列表时，系统会为列表分配“初始容量”，该容量可能超出实际需求
- 扩容机制通常是按照特定倍率（例如 2 倍）进行扩容的，扩容后的容量也可能超出实际需求
- 链表节点需要额外存储指针，因此链表节点占用的空间相对较大
综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。
14 栈的应用
1.4.1 典型应用场景
- 浏览器中的后退与前进、软件中的撤销和反撤销。
- 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数在上下文信息。在递归函数中，向下递归阶段会不断执行入栈操作，而向上回溯阶段会不断执行出栈操作。
1.4.2 算法案例-符号匹配问题
符号匹配时许多编程语言中的常见问题, 括号匹配问题只是一个特例.符号匹配是指正确的匹配和嵌套左右对应的符号.
- 符号匹配的例子
- {{([][])}()}
- [][][]{}
- 符号不匹配的例子
- ([)]
- ((()]))
2. 队列
2.1 概念
队列是一种操作受限的线性表, 添加操作(入队)发生在”尾部”(rear), 移除操作(出队)则发生在”头部”(front), 简称队.最新添加的元素必须在队列的尾部等待, 在队列中时间最长的元素则排在最前面.这种排序原则被称为FIFO(first-in first-out), 即先进后出.在现实生活中, 将小球刚入管道中就是典型的队列结构.
2.2 相关方法
- Queue() 创建空队列
- enqueue() 队列尾部添加元素, 无返回值
- dequeue() 队列头部删除元素, 返回该元素
- isEmpty() 判断是否为空, 为空返回True, 否则返回False
- size() 返回队列的长度
2.3 队列实现
为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。
2.3.1 列表实现(了解)
用列表实现的队列, 添加操作是在列表的开头, 时间复杂度为O(n). 显然使用列表创建队列是不合适的. 有没有什么线性数据结构对其开头和结尾添加或删除元素其时间复杂度都为O(1), 有的, 那就是用链表linkedlist创建队列.
2.3.2 链表实现
3. 双向队列 double‑ended queue
3.1 概念
在队列中，我们仅能删除头部元素或在尾部添加元素。双向队列提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。
3.2 相关方法
- Deque() 创建空的双端队列
- addfront(item) 将元素添加到双端队列的前端, 无返回值
- addrear(item) 将元素添加到双端队列的尾端, 无返回值
- removefront() 将元素从双端队列的前端删除, 返回该元素
- removerear() 将元素从双端队列的尾端删除, 返回该元素
- isempty() 判断双端队列是否为空, 为空返回True, 否则返回False
- size() 返回双端队列的长度
在Python中，已经实现了双向队列：
3.3 双向队列实现
双向队列的实现与队列的类似，可以选择链表或数组作为底层数据结构来实现
3.4 双向队列应用
双向队列兼具栈与队列的逻辑， 因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过50 时，软件需要在栈底（队首）执行删除操作。 但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。
3.4.1 回文检测器
回文是指从前往后读和从后往前读都是一样的字符串.需要设计一个回文检测器严重给定的字符串是否是回文.
4. queue模块
queue模块定义了Queue, LifoQueue, PriorityQueue, SimpleQueue四个不同类型的队列, 它们之间的区别在于数据入队列之后出队列的顺序不同
4.1 类型介绍
4.1.1 Queue
先进先出(first-in first-out)队列, 继承自deque双端队列, 由链表实现.
4.1.2 LifoQueue
后进先出队列，即栈结构, 这个类继承自Queue, 重写初始化方法用列表实现, 使用方式同Queue.
3.1.3 PriorityQueue
优先队列, 这个类也继承自Queue类, 并重写了入队, 出队的方法.
- 它里面是堆, 用列表实现的堆, 构建的是小顶堆
- 元素可以存储任意值, 但是优先队列内部是直接进行元素大小的比较的, 不同类型比较可能抛出异常.
- 入队时, 将元素加入到列表末尾. 然后进行小顶堆调整.
- 出队时, 将索引0即堆顶处最小值弹出, 然后将最后一个元素放到堆顶, 重新堆调整
4.2 相关方法
Queue、LifoQueue、PriorityQueue 和 SimpleQueue 四种队列定义的对象均提供了以下函数使用方法，下面以 Queue 队列为例进行介绍
SimpleQueue 是 Python 3.7 版本中新加入的特性，与 Queue、LifoQueue 和 PriorityQueue 三种队列相比缺少了 task_done 和 join 的高级使用方法，所以才会取名叫 Simple 了
4.2.1 方法
1、初始化
- 创建FIFO队列, 返回Queue对象
- maxsize为整数, 设置队列的最大长度
- maxsize小于等于0, 队列长度没有限制
2、出队
- 从队列中移除元素并返回这个元素
- block为阻塞, timeout为超时
- block为True, 是阻塞, timeout为None就是一直阻塞
- block为True, 但是timeout有值, 就阻塞到一定秒数抛出异常
- block为False, 是非阻塞, timeout将被忽略, 要么成功返回一个元素, 要么抛出empty异常.
3、无等待出队
- 等价于get(False), 也就是说要么成功返回一个元素, 要么抛出empty异常.
- 但是queue的这种阻塞效果, 需要多线程来演示.
4、入队
- 把一个元素item加入到队列中去
- block=True, timeout=None, 一直阻塞至有空位放元素
- block=True, timeout=5, 阻塞5s就抛出Full异常
- block=False, timeout失效, 立即返回, 能塞进去就塞, 不能则返回抛出异常
5、无等待入队
- 等价于put(item, False), 也就是能塞进去就塞, 不能则返回抛出queue.Full异常.
7、其他方法:
4.2.2 异常
- queue.Empty异常:
- 当队列中没有数据元素时，取出队列中的数据会引发 queue.Empty 异常，主要是不正当使用 get() 和 get_nowait() 引起的。
- queue.Full异常
- 当队列数据元素容量达到上限时，继续往队列中放入数据会引发 queue.Empty 异常，主要是不正当使用 put() 和 put_nowait() 引起的
4.2.3 演示
4.3 应用
4.3.1 约瑟夫环问题(杀人游戏)
n个人(n个人的标签从1到n)排成一圈, 从第一个人开始数数, 数到三, 这个人被杀, 下个人重新数数, 问最后一个人是谁.
4.3.2 线程中应用
生产者和消费者线程分别生产数据和消费数据，先生产后消费。采用 task_done 和 join 确保处理信息在多个线程间安全交换，生产者生产的数据能够全部被消费者消费掉。