3.3.什么是栈
Last updated
Last updated
栈(有时称为“后进先出栈”)是一个项的有序集合,其中添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。
栈的底部很重要,因为在栈中靠近底部的项是存储时间最长的。最近添加的项是最先会被移除的。这种排序原则有时被称为 LIFO,后进先出。它基于在集合内的时间长度做排序。较新的项靠近顶部,较旧的项靠近底部。
栈的例子很常见。几乎所有的自助餐厅都有一堆托盘或盘子,你从顶部拿一个,就会有一个新的托盘给下一个客人。想象桌上有一堆书(Figure 1), 只有顶部的那本书封面可见,要看到其他书的封面,只有先移除他们上面的书。Figure 2 展示了另一个栈,包含了很多 Python 对象。
Figure 2
和栈相关的最有用的想法之一来自对它的观察。假设从一个干净的桌面开始,现在把书一本本叠起来,你在构造一个栈。考虑下移除一本书会发生什么。移除的顺序跟刚刚被放置的顺序相反。栈之所以重要是因为它能反转项的顺序。插入跟删除顺序相反,Figure 3 展示了 Python 数据对象创建和删除的过程,注意观察他们的顺序。
Figure 3
想想这种反转的属性,你可以想到使用计算机的时候所碰到的例子。例如,每个 web 浏览器都有一个返回按钮。当你浏览网页时,这些网页被放置在一个栈中(实际是网页的网址)。你现在查看的网页在顶部,你第一个查看的网页在底部。如果按‘返回’按钮,将按相反的顺序浏览刚才的页面。
Figure 1