Question

当你结束了对本书的学习，开始使用 Python 完成各种各样的商业数据处理与分析任务时，就会越来越觉得掌握更多的数据结构是非常重要的。通过学习这些概念，你会极大地提高解决问题的能力，在面临问题时，不仅可以提出各种不同的解决方案，还可以在不同的方案之中做出权衡取舍。同时，你也可以根据实际情况恰当地选择数据结构，来更快速有效地保存、处理和分析你的数据。

你还需要了解的其他数据结构包括栈、队列、图和树。在特定情况下，这些数据结构可以更有效地保存和检索数据，能够比列表、元组和字典更好地使用内存。

9.3.1　栈

栈是一个项目的有序集合，既可以向栈中的一端添加一个项目，又可以从同一端删除一个项目，但一次只能添加或删除一个项目。可以添加和删除项目的一端称为栈顶，相反的一端称为栈底。给定了栈顶和栈底之后，栈顶附近的项目停留在栈中的时间要少于栈底附近的项目。另外，从栈中删除项目的顺序和向栈中添加项目的顺序是相反的。这个特性称为 LIFO（last in, first out，后入先出）。

可以将栈想象为自助餐厅中的一叠盘子。要想产生一叠盘子，可以先向柜台上放一个盘子，然后向第一个盘子上面再放一个盘子，并一直重复这个操作。要想减少这叠盘子的数量，就要从顶端拿走一个盘子。你可以在任何时候增加或减少一个盘子，但是必须一直从顶端增加或减少。

有很多数据处理和分析问题适合使用栈来解决。人们使用栈来分配和访问计算机内存、保存命令行参数和函数参数、解析表达式、反转数据项、保存与回溯 URL，等等。

9.3.2　队列

队列是一个项目的有序集合，既可以向队列的一端添加项目，又可以从队列的另一端删除项目。在队列中，可以向队列后端添加项目，这样项目会依次向前移动，并在前端被移出队列。给定了队列的前端和后端，队列后端附近的项目停留在队列中的时间要少于队列前端附近的项目。这个特性称为 FIFO（first in, first out，先入先出）。

想象一下你曾经排过的一个秩序良好的队列，或者队伍。不管是在主题公园、电影院，还是在杂货店，你进入队列，排在末尾，然后向前移动直到队列最前方，这时你可以买票或接受服务，然后你就离开了队列。

有很多数据处理和分析问题适合使用队列来解决。人们使用队列来处理打印机上的打印任务、控制计算机进程等待资源、优化队列和网络流程，等等。

9.3.3　图

图是一组结点（也称为顶点）和连接结点的边的集合。边可以是有方向的，表示两个结点之间的方向，也可以是无方向的，仅表示两个结点之间的连接。边还可以具有权重，表示两个结点之间的关系，根据具体问题的情况，权重可以不同。

想象任何表示人群、地点和主题之间关系的图。例如，可以想象一下表示演员、导演和电影之间关系的图，演员、导演和电影就是图中的结点，结点之间的边表示哪个演员出演了这部电影，或者哪个导演指导了这部电影。再比如，可以将城市作为结点，结点之间的边表示从一个城市到另一个城市之间的道路。这样的边就可以使用权重表示两个城市之间的距离。

有很多数据处理和分析问题适合使用图来解决。人们使用图来表示供应商、客户和产品之间的关系，或者实体之间的关系，还使用图来表示地图，以及不同类型资源的储量和需求量。

9.3.4　树

从数据结构意义上说，树是图的一种特殊形式，它由一组层次化的结点和边组成。在树中，有一个最顶层的结点，称为根结点。根结点可以有任意数量的子结点，每个子结点也可以有任意数量的子结点。一个子结点只能有一个父节点。如果每个结点有多达两个子结点，那么这样的树就被称为二叉树。

考虑一下 HTML 文件中的元素。在 html 标签之中，有 head 标签和 body 标签。在 head 标签之中，有 meta 标签和 title 标签。在 body 标签之中，有 h1、div、form 和 ul 标签。如果用树结构表示这些标签的话，就可以将 html 标签看作根结点，它有两个子结点，head 标签和 body 标签。在表示 head 标签的结点下面，有 meta 标签和 title 标签。在表示 body 标签的结点下面，有 h1 标签、div 标签、form 标签和 ul 标签。

有很多数据处理和分析问题适合使用树来解决。人们使用树来建立计算机中的文件系统、管理层次化的数据、使信息更易于检索，以及表示句子中的短语结构等。

本节简单介绍了一些经典的数据结构。如果想学习更多如何在 Python 中使用这些数据结构的知识，可以参考 Brad Miller 和 David Ranum 的在线著作 Problem Solving with Algorithms and Data Structures Using Python（http://interactivepython.org/runestone/static/pythonds/index.html）。

知道这些数据结构的存在对你是很有帮助的，当你的程序运行得不是那么好的时候，可以试试这些数据结构。了解并知道在什么情况下应该使用哪种数据结构，你就有能力去解决各种规模庞大、难度系数高的问题，并能提高脚本的性能，节省处理时间，提高内存的利用效率。