一些关于编程语言的知识 || yeye 想变强

以下内容来自ai（豆包），为了我自己的学习，我把它记录下来。

STL

一、STL 到底是什么？

STL 是 Standard Template Library（标准模板库） 的缩写，是 C++ 标准库的核心组成部分，本质是一套 通用、可复用的模板类/函数库。

简单说：

它是 C++ 官方提供的“工具集”，不用自己写基础数据结构（比如栈、队列、数组、链表）和算法（比如排序、查找、遍历），直接调用就行；
核心优势是 模板化（跨数据类型通用，比如一个 vector 既可以存 int，也能存 string）、高效（底层用最优算法实现）、标准化（所有符合 C++ 标准的编译器都支持，比如 GCC、Clang、MSVC）。

STL 主要包含 6 大组件，日常开发最常用的是前 4 个：

组件	作用
容器（Container）	存储数据的“容器”（比如 `vector` 动态数组、`list` 链表、`stack` 栈、`map` 字典）
算法（Algorithm）	操作容器数据的算法（比如 `sort` 排序、`find` 查找、`reverse` 反转）
迭代器（Iterator）	连接容器和算法的“桥梁”（类似指针，遍历容器数据）
适配器（Adaptor）	对现有容器“包装改造”，改变其接口（比如 `stack` 就是对其他容器的适配器）
函数对象（Functor）	行为类似函数的对象（配合算法使用，比如自定义排序规则）
分配器（Allocator）	负责容器的内存分配/释放（底层细节，用户一般不用关心）

二、STL 中 `stack` 的实现原理

stack（栈）的核心特性是 LIFO（后进先出）：只能从“栈顶”插入（push）、删除（pop）和访问（top）数据，不能随机访问中间元素。

关键结论：`stack` 不是独立的容器，而是「容器适配器」

STL 的 stack 本身不存储数据，它是对一个 底层容器（Underlying Container） 进行“包装”，限制了其接口（只暴露栈需要的 push/pop/top 等），底层数据的存储、内存管理全靠这个“被包装的容器”。

1. 默认底层容器是什么？

C++ 标准规定，stack 的 默认底层容器是 deque（双端队列）。
选择 deque 的原因很简单：deque 支持 两端高效插入/删除（时间复杂度 O(1)），而栈只需要操作“一端”（栈顶），用 deque 刚好匹配，且 deque 没有 vector 扩容时的拷贝开销，效率更高。

2. 可以自定义底层容器吗？

可以！stack 是模板类，允许用户指定底层容器，只要这个容器支持以下 3 个核心操作即可：

push_back()：在尾部插入元素（栈顶对应容器尾部）；
pop_back()：删除尾部元素；
back()：访问尾部元素。

满足条件的容器有 vector、list、deque，比如：

#include <stack>
#include <vector>
#include <list>

// 1. 默认底层容器：deque
std::stack<int> st1;

// 2. 自定义底层容器为 vector
std::stack<int, std::vector<int>> st2;

// 3. 自定义底层容器为 list
std::stack<int, std::list<int>> st3;

3. `stack` 的核心接口实现（伪代码）

stack 的接口非常简单，本质就是“转发”到底层容器的对应操作，伪代码能直观体现：

template <typename T, typename Container = std::deque<T>>
class stack {
private:
    Container c;  // 底层容器（被包装的对象）
public:
    // 入栈：调用底层容器的 push_back()
    void push(const T& x) { c.push_back(x); }
    
    // 出栈：调用底层容器的 pop_back()（注意：不返回元素）
    void pop() { c.pop_back(); }
    
    // 访问栈顶：调用底层容器的 back()
    T& top() { return c.back(); }
    
    // 栈是否为空：调用底层容器的 empty()
    bool empty() const { return c.empty(); }
    
    // 栈的大小：调用底层容器的 size()
    size_t size() const { return c.size(); }
};

从伪代码能看出来：stack 没有自己的“数据存储逻辑”，所有操作都依赖底层容器，它只做了一件事——隐藏底层容器的其他接口（比如 vector 的 operator[] 随机访问），只暴露栈需要的 LIFO 接口。

三、补充：`stack` 为什么不叫“容器”而叫“适配器”？

容器（比如 vector、list）：是“原始存储容器”，支持完整的元素访问/操作（比如 vector 可以随机访问、list 可以双向遍历）；
适配器（比如 stack、queue）：是“包装器”，不提供原始存储，而是基于现有容器，通过“限制接口”来实现特定的数据结构行为（栈的 LIFO、队列的 FIFO）。

简单说：适配器是“改造现有容器”，而容器是“原生存储数据”。

总结

STL 是 C++ 标准库的核心，是通用的模板工具集，包含容器、算法、迭代器等组件；
STL 的 stack 是 容器适配器，底层不存数据，依赖其他容器实现；
默认底层容器是 deque，也可指定 vector 或 list（需支持 push_back/pop_back/back）；
stack 的所有接口（push/pop/top）都是转发到底层容器的对应操作，核心是实现 LIFO 特性。

deque

from collections import deque 是 Python 中导入内置容器类 deque 的标准语法，以下是关于 deque 的详细解析、用法和场景说明：

一、核心基础：什么是 deque？

全称：Double-Ended Queue（双端队列）
本质：Python 标准库 collections 模块提供的高效双端队列数据结构，支持两端（队首/队尾）的快速插入和删除操作。
与 list 的区别：
- list 基于数组实现，队首插入/删除（如 list.insert(0, x)、list.pop(0)）时间复杂度为 O(n)（需移动所有元素）；
- deque 基于双向链表（或类似优化结构）实现，两端操作时间复杂度均为 O(1)，效率远超 list。

二、基本用法（需先导入 `deque`）

1. 初始化 deque

from collections import deque

# 1. 空队列
dq = deque()

# 2. 从可迭代对象（列表、字符串、元组等）初始化
dq1 = deque([1, 2, 3])       # deque([1, 2, 3])
dq2 = deque("abc")           # deque(['a', 'b', 'c'])
dq3 = deque((4, 5, 6), maxlen=5)  # 限制最大长度为5（超出会自动丢弃另一端元素）

2. 两端插入操作（核心优势）

方法	功能	示例	结果
`append(x)`	队尾添加元素 x	`dq1.append(4)`	`deque([1, 2, 3, 4])`
`appendleft(x)`	队首添加元素 x	`dq1.appendleft(0)`	`deque([0, 1, 2, 3, 4])`
`extend(iterable)`	队尾批量添加可迭代对象	`dq1.extend([5, 6])`	`deque([0,1,2,3,4,5,6])`
`extendleft(iterable)`	队首批量添加（逆序插入）	`dq1.extendleft([-2, -1])`	`deque([-1, -2, 0,1,2,3,4,5,6])`

注意 extendleft：会将可迭代对象的元素逆序插入队首（如 extendleft([a,b]) 等价于 appendleft(b) 后 appendleft(a)）。

3. 两端删除操作

方法	功能	示例	结果
`pop()`	队尾删除并返回元素	`dq1.pop()`	返回 `6`，队列变为 `deque([-1,-2,0,1,2,3,4,5])`
`popleft()`	队首删除并返回元素	`dq1.popleft()`	返回 `-1`，队列变为 `deque([-2,0,1,2,3,4,5])`
`clear()`	清空队列	`dq1.clear()`	`deque([])`

4. 其他常用方法

maxlen 属性：获取队列最大长度（初始化时指定，不可修改）

dq = deque([1,2,3], maxlen=3)
print(dq.maxlen)  # 3
dq.append(4)      # 超出maxlen，队首元素1被自动丢弃
print(dq)         # deque([2, 3, 4])

rotate(n)：队列旋转（默认 n=1，队尾元素移到队首；n=-1 则队首元素移到队尾）

dq = deque([1,2,3,4])
dq.rotate(1)   # 右旋转1位：4→队首
print(dq)      # deque([4, 1, 2, 3])
dq.rotate(-2)  # 左旋转2位：4、1→队尾
print(dq)      # deque([2, 3, 4, 1])

count(x)：统计元素 x 的出现次数
1
deque([1,2,2,3]).count(2) # 2
remove(x)：删除第一个出现的元素 x（不存在则抛 ValueError）
1
2
3
dq = deque([1,2,3,2])
dq.remove(2)
print(dq) # deque([1, 3, 2])

三、典型应用场景

1. 实现队列（FIFO：先进先出）

from collections import deque

queue = deque()
# 入队（队尾添加）
queue.append("a")
queue.append("b")
# 出队（队首删除）
print(queue.popleft())  # "a"
print(queue.popleft())  # "b"

2. 实现栈（LIFO：后进先出）

（直接用 append() 和 pop()，等价于栈的压栈/出栈）

stack = deque()
stack.append(1)
stack.append(2)
print(stack.pop())  # 2（后进先出）
print(stack.pop())  # 1

3. 滑动窗口问题（利用 `maxlen` 自动维护窗口大小）

例如：求数组中每个位置的前 k 个元素的平均值

from collections import deque

def sliding_average(nums, k):
    dq = deque(maxlen=k)
    averages = []
    for num in nums:
        dq.append(num)
        if len(dq) == k:  # 窗口满了才计算平均值
            averages.append(sum(dq)/k)
    return averages

print(sliding_average([1,2,3,4,5,6], 3))  # [2.0, 3.0, 4.0, 5.0]

4. 广度优先搜索（BFS）

BFS 算法的核心是用队列存储待访问节点，deque 的 popleft() 效率远高于 list.pop(0)：

from collections import deque

def bfs(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()  # 队首出队
        result.append(node.val)
        # 子节点入队
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

四、总结

deque 是 Python 中高效双端队列，核心优势是两端插入/删除 O(1) 时间复杂度；
功能覆盖队列、栈、滑动窗口等场景，比 list 更适合频繁操作两端的场景；
需通过 from collections import deque 导入，支持 maxlen、rotate 等实用功能，是 Python 开发中高频使用的容器类。

一些关于编程语言的知识

STL