算法(4th ed)(121):基础——背包、队列和栈 5.1.6

阅读数:18 2019 年 11 月 6 日 07:29

算法(4th ed)(121):基础——背包、队列和栈 5.1.6

(API:下压栈)

下压栈(或简称)是一种基于后进先出(LIFO)策略的集合类型,如图 1.3.3 所示。当你的邮件在桌上放成一叠时,使用的就是栈。新邮件来到时你将它们放在最上面,当你有空时你会一封一封地从上到下阅读它们。现在人们应付的纸质品比以前少得多,但计算机上的许多常用程序遵循相同的组织原则。例如,许多人仍然用栈的方式存放电子邮件——在收信时将邮件压入(push)最顶端,在取信时从最顶端将它们弹出(pop),且第一封一定是最新的邮件(后进,先出)。这种策略的好处是我们能够及时看到感兴趣的邮件,坏处是如果你不把栈清空,某些较早的邮件可能永远也不会被阅读。你在网上冲浪时很可能会遇到栈的另一个例子。点击一个超链接,浏览器会显示一个新的页面(并将它压入一个栈)。你可以不断点击超链接并访问新页面,但总是可以通过点击“回退”按钮重新访问以前的页面(从栈中弹出)。栈的后进先出策略正好能够提供你所需要的行为。当用例使用 foreach 语句迭代遍历栈中的元素时,元素的处理顺序和它们被压入的顺序正好相反。在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的相对顺序。例如,右侧的用例 Reverse 将会把标准输入中的所有整数逆序排列,同样它也无需预先知道整数的多少。在计算机领域,栈具有基础而深远的影响,下一节我们会仔细研究一个例子,以说明栈的重要性。

算法(4th ed)(121):基础——背包、队列和栈 5.1.6

图 1.3.3 下压栈的操作

复制代码
public class Reverse
{
public static void main(String[] args)
{
Stack<Integer> stack;
stack = new Stack<Integer>();
while (!StdIn.isEmpty())
stack.push(StdIn.readInt());
for (int i : stack)
StdOut.println(i);
}
}
`Stack` 的用例

评论

发布