数据结构和算法 (DSA)
通常被认为是一个令人生畏的话题——一种常见的误解。它们是技术领域最具创新性概念的基础，对于工作/实习申请者和有经验的程序员的职业发展都至关重要。掌握DSA意味着你能够使用你的计算和算法思维来解决前所未见的问题，并为任何科技公司的价值做出贡献（包括你自己的！）。通过了解它们，您可以提高代码的可维护性、可扩展性和效率。
话虽如此，我决定在CSDN新星计划挑战期间将我所了解的数据结构和算法集中起来。本文旨在使 DSA 看起来不像人们认为的那样令人生畏。它包括 15 个最有用的数据结构和 15 个最重要的算法，可以帮助您在学习中和面试中取得好成绩并提高您的编程竞争力。后面等我还会继续对这些数据结构和算法进行进一步详细地研究讲解。
一、数据结构
1. 数组（Arrays）
数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。
它们是做什么用的？
想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）！
特性
元素的值按顺序放置，并通过从 0 到数组长度的索引访问；
数组是连续的内存块；
它们通常由相同类型的元素组成（这取决于编程语言）；
元素的访问和添加速度很快；搜索和删除不是在 O(1) 中完成的。
2. 链表（Linked Lists）
链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。
它们是做什么用的？
链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。
特性
它们分为三种类型：单独的、双重的和圆形的；
元素不存储在连续的内存块中；
完美的优秀内存管理（使用指针意味着动态内存使用）；
插入和删除都很快；访问和搜索元素是在线性时间内完成的。
3. 堆栈（Stacks）
堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。
堆栈可以使用数组或链表来实现。
它们是做什么用的？
现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。
堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。
另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。
特性
您一次只能访问最后一个元素（顶部的元素）；
一个缺点是，一旦您从顶部弹出元素以访问其他元素，它们的值将从堆栈的内存中丢失；
其他元素的访问是在线性时间内完成的；任何其他操作都在 O(1) 中。
4. 队列（Queues）
队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。
它们是做什么用的？
这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。
一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 - 更多关于它们的信息）中是必不可少的。它是使用堆实现的。
另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。
特性
我们只能直接访问引入的“最旧”元素；
搜索元素将从队列的内存中删除所有访问过的元素；
弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。
5. Map 和 哈希表（Hash Table）
Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。
哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。
最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。
理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。
它们是做什么用的？
Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。
通讯录也是一张Map。每个名字都有一个分配给它的电话号码。
另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。
特性
键是唯一的（没有重复）；
抗碰撞性：应该很难找到具有相同键的两个不同输入；
原像阻力：给定值 H，应该很难找到键 x，使得h(x)=H；
第二个原像阻力：给定一个键和它的值，应该很难找到另一个具有相同值的键；
术语：
“map”：Java、C++；
“dictionary”：Python、JavaScript、.NET；
“associative array"：PHP。
因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。
