Zxy's Blog

双向队列 在队列中，我们仅能删除头部元素或在尾部添加元素。如下图所示，双向队列（double-ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。 双向队列常用操作 双向队列的常用操作如下表所示，具体的方法名称需要根据所使用的编程语言来确定。 表   双向队列操作效率 方法名 描述 时间复杂度 push_first() 将元素添加至队首 O(1)O(1)O(1) push_last() 将元素添加至队尾 O(1)O(1)O(1) pop_first() 删除队首元素 O(1)O(1)O(1) pop_last() 删除队尾元素 O(1)O(1)O(1) peek_first() 访问队首元素 O(1)O(1)O(1) peek_last() 访问队尾元素 O(1)O(1)O(1) 同样地，我们可以直接使用编程语言中已实现的双向队列类： 12345678910111213141516171819202122232425from collections import deque#...

小结 重点回顾 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。 在时间效率方面，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会劣化至 O(n)O(n)O(n) 。相比之下，栈的链表实现具有更为稳定的效率表现。 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内存空间比数组元素更大。 队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现。在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似。 双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作。 Q & A Q：浏览器的前进后退是否是双向链表实现？ 浏览器的前进后退功能本质上是“栈”的体现。当用户访问一个新页面时，该页面会被添加到栈顶；当用户点击后退按钮时，该页面会从栈顶弹出。使用双向队列可以方便地实现一些额外操作，这个在“双向队列”章节有提到。 Q：在出栈后，是否需要释放出栈节点的内存？ 如果后续仍需要使用弹出节点，则不需要释放内存。若之后不需要用到，Java 和 Python...

队列 队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。 如下图所示，我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。 队列常用操作 队列的常见操作如下表所示。需要注意的是，不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。 表   队列操作效率 方法名 描述 时间复杂度 push() 元素入队，即将元素添加至队尾 O(1)O(1)O(1) pop() 队首元素出队 O(1)O(1)O(1) peek() 访问队首元素 O(1)O(1)O(1) 我们可以直接使用编程语言中现成的队列类： 12345678910111213141516171819202122232425from collections import deque# 初始化队列# 在 Python 中，我们一般将双向队列类 deque 当作队列使用# 虽然 queue.Queue()...

栈 栈（stack）是一种遵循先入后出逻辑的线性数据结构。 我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。 如下图所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。 栈的常用操作 栈的常用操作如下表所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push()、pop()、peek() 命名为例。 表   栈的操作效率...

小结 重点回顾 数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和分散空间存储。两者的特点呈现出互补的特性。 数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。 链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、环形链表、双向链表。 列表是一种支持增删查改的元素有序集合，通常基于动态数组实现。它保留了数组的优势，同时可以灵活调整长度。 列表的出现大幅提高了数组的实用性，但可能导致部分内存空间浪费。 程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。 缓存通过缓存行、预取机制以及空间局部性和时间局部性等数据加载机制，为 CPU 提供快速数据访问，显著提升程序的执行效率。 由于数组具有更高的缓存命中率，因此它通常比链表更高效。在选择数据结构时，应根据具体需求和场景做出恰当选择。 Q &...

内存与缓存 * 在本章的前两节中，我们探讨了数组和链表这两种基础且重要的数据结构，它们分别代表了“连续存储”和“分散存储”两种物理结构。 实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。 计算机存储设备 计算机中包括三种类型的存储设备：硬盘（hard disk）、内存（random-access memory, RAM）、缓存（cache memory）。下表展示了它们在计算机系统中的不同角色和性能特点。 表   计算机的存储设备 硬盘 内存 缓存 用途 长期存储数据，包括操作系统、程序、文件等 临时存储当前运行的程序和正在处理的数据 存储经常访问的数据和指令，减少 CPU 访问内存的次数 易失性 断电后数据不会丢失 断电后数据会丢失 断电后数据会丢失 容量 较大，TB 级别 较小，GB 级别 非常小，MB 级别 速度 较慢，几百到几千 MB/s 较快，几十 GB/s 非常快，几十到几百 GB/s 价格 较便宜，几毛到几元 / GB 较贵，几十到几百元 / GB 非常贵，随 CPU...

列表 列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。 链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。 数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间浪费。 为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。 实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List...

链表 内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。 链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。 观察上图，链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。 链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。 尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为 null、nullptr 和 None 。 在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。 如以下代码所示，链表节点 ListNode...

数组 数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。下图展示了数组的主要概念和存储方式。 数组常用操作 初始化数组 我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为 000 ： 123# 初始化数组arr: list[int] = [0] * 5 # [ 0, 0, 0, 0, 0 ]nums: list[int] = [1, 3, 2, 5, 4] 访问元素 数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引，我们可以使用下图所示的公式计算得到该元素的内存地址，从而直接访问该元素。 观察上图，我们发现数组首个元素的索引为 000 ，这似乎有些反直觉，因为从 111 开始计数会更自然。但从地址计算公式的角度看，索引本质上是内存地址的偏移量。首个元素的地址偏移量是 000 ，因此它的索引为 000...

Python基础