普林斯顿算法讲义（一）(2)-阿里云开发者社区

普林斯顿算法讲义（一）（1）https://developer.aliyun.com/article/1484167

该代码打印字符串"2 ones"。
对象作为参数。 您可以将对象作为参数传递给方法。Java 将调用程序中的参数值的副本传递给方法。这种安排称为按值传递。如果您将一个指向Counter类型对象的引用传递给方法，Java 将传递该引用的副本。因此，该方法无法更改原始引用（使其指向不同的Counter），但可以更改对象的值，例如通过使用引用调用increment()。
对象作为返回值。 您还可以将对象作为方法的返回值。该方法可能会返回作为参数传递给它的对象，就像 FlipsMax.java 中的情况，或者它可能创建一个对象并返回对其的引用。这种能力很重要，因为 Java 方法只允许一个返回值——使用对象使我们能够编写代码，实际上返回多个值。
数组是对象。 在 Java 中，任何非原始类型的值都是对象。特别是，数组是对象。与字符串一样，对数组有特殊的语言支持：声明、初始化和索引。与任何其他对象一样，当我们将数组传递给方法或在赋值语句的右侧使用数组变量时，我们只是复制数组引用，而不是数组本身的副本。
对象数组。 数组条目可以是任何类型。当我们创建一个对象数组时，需要分两步进行：使用数组构造函数的括号语法创建数组；为数组中的每个对象创建一个标准构造函数。Rolls.java 模拟掷骰子，使用Counter对象数组来跟踪每个可能值出现的次数。

抽象数据类型的示例。

几何对象。面向对象编程的一个自然示例是为几何对象设计数据类型。

Point2D.java 是用于平面上的点的数据类型。
Interval1D.java 是用于一维区间的数据类型。
Interval2D.java 是用于二维区间的数据类型。

信息处理。抽象数据类型提供了一个自然的机制来组织和处理信息。信息

Date.java 是一个表示日期、月份和年份的��据类型。
Transaction.java 是一个表示客户、日期和金额的数据类型。

累加器。 Accumulator.java 定义了一个 ADT，为客户提供了维护数据值的运行平均值的能力。例如，我们在本书中经常使用这种数据类型来处理实验结果。VisualAccumulator.java 是一个增强版本，还会绘制数据（灰色）和运行平均值（红色）。
字符串。 Java 的String数据类型是一个重要且有用的 ADT。String是char值的索引序列。String有几十种实例方法，包括以下内容： String有特殊的语言支持用于初始化和连接：我们可以使用字符串字面量来创建和初始化字符串，而不是使用构造函数；我们可以使用+运算符来连接字符串，而不是调用concat()方法。
输入和输出再探讨。 第 1.1 节的StdIn、StdOut和StdDraw库的一个缺点是它们限制了我们在任何给定程序中只能使用一个输入文件、一个输出文件和一个绘图。通过面向对象编程，我们可以定义类似的机制，允许我们在一个程序中使用多个输入流、输出流和绘图。具体来说，我们的标准库包括支持多个输入和输出流的数据类型 In.java、Out.java 和 Draw.java。

实现抽象数据类型。

我们使用 Java 类来实现 ADTs，将代码放在与类同名的文件中，后面跟着.java 扩展名。文件中的第一条语句声明实例变量，定义数据类型的值。在实例变量之后是构造函数和实例方法，实现对数据类型值的操作。

实例变量. 为了定义数据类型的值（每个对象的状态），我们声明实例变量的方式与声明局部变量的方式非常相似。每个实例变量对应着许多值（对应数据类型的每个实例对象）。每个声明都由可见性修饰符修饰。在 ADT 实现中，我们使用private，使用 Java 语言机制来强制执行 ADT 的表示应该对客户端隐藏，还可以使用final，如果该值在初始化后不会更改。
构造函数. 构造函数建立对象的标识并初始化实例变量。构造函数总是与类同名。我们可以重载名称并具有具有不同签名的多个构造函数，就像方法一样。如果没有定义其他构造函数，则隐式存在一个默认无参数构造函数，没有参数，并将实例值初始化为默认值。原始数值类型的默认值为 0，boolean为false，null。
实例方法. 实例方法指定数据类型的操作。每个实例方法都有一个返回类型，一个签名（指定其名称和参数变量的类型和名称），以及一个主体（包括一系列语句，包括一个返回语句，将返回类型的值提供给客户端）。当客户端调用方法时，参数值（如果有）将用客户端值初始化，语句将执行直到计算出返回值，并将该值返回给客户端。实例方法可以是public（在 API 中指定）或private（用于组织计算且不可用于客户端）。
作用域. 实例方法使用三种类型的变量：参数变量，局部变量和实例变量。前两者与静态方法相同：参数变量在方法签名中指定，并在调用方法时用客户端值初始化，局部变量在方法主体内声明和初始化。参数变量的作用域是整个方法；局部变量的作用域是定义它们的块中的后续语句。实例变量保存类中对象的数据类型值，其作用域是整个类（在存在歧义时，可以使用this前缀来标识实例变量）。

设计抽象数据类型。

我们将与设计数据类型相关的重要信息放在一个地方供参考，并为本书中的实现奠定基础。

封装. 面向对象编程的一个特点是它使我们能够将数据类型封装在其实现中，以促进客户端和数据类型实现的分开开发。封装实现了模块化编程。
设计 APIs.在构建现代软件中最重要且最具挑战性的步骤之一是设计 APIs。理想情况下，API 将清晰地阐明所有可能输入的行为，包括副作用，然后我们将有软件来检查实现是否符合规范。不幸的是，理论计算机科学中的一个基本结果，即规范问题，意味着这个目标实际上是不可能实现的。在设计 API 时存在许多潜在的陷阱：

过于难以实现，使得开发变得困难或不可能。
过于难以使用，导致复杂的客户端代码。
过于狭窄，省略了客户端需要的方法。
过于广泛，包含许多任何客户端都不需要的方法。
过于一般，提供没有用的抽象。
过于具体，提供的抽象太过模糊，无用。
过于依赖特定表示，因此不能使客户端代码摆脱表示的细节。

总之，为客户端提供他们需要的方法，而不是其他方法。
算法和 ADT.数据抽象自然适合于算法的研究，因为它帮助我们提供一个框架，可以精确指定算法需要完成的任务以及客户端如何使用算法。例如，我们在本章开头的白名单示例自然地被视为 ADT 客户端，基于以下操作：

从给定值数组构造一个 SET。
确定给定值是否在集合中。

这些操作封装在 StaticSETofInts.java 和 Allowlist.java 中。
接口继承. Java 提供了语言支持来定义对象之间的关系，称为继承。我们考虑的第一种继承机制称为子类型化，它允许我们通过在接口中指定一组每个实现类必须包含的共同方法来指定否则无关的类之间的关系。我们使用接口继承进行比较和迭代。
实现继承. Java 还支持另一种继承机制，称为子类化，这是一种强大的技术，使程序员能够在不从头开始重写整个类的情况下更改行为和添加功能。这个想法是定义一个��承实例方法和实例变量的新类（子类），从另一个类（超类）继承。我们在本书中避免使用子类化，因为它通常违反封装。这种方法的某些残留物内置在 Java 中，因此不可避免：具体来说，每个类都是Object的子类。
字符串转换. 每种 Java 类型都从Object继承了toString()。这种约定是 Java 自动将连接运算符+的一个操作数转换为String的基础，只要另一个操作数是String。我们通常包含重写默认toString()的实现，如 Date.java 和 Transaction.java。
包装类型. Java 提供了内置的引用类型，称为包装类型，每种原始类型对应一个：

基本类型	包装类型
`boolean`	Boolean
`byte`	Byte
`char`	Character
`double`	Double
`float`	Float
`int`	Integer
`long`	Long
`short`	Short

Java 在必要时会自动将基本类型转换为包装类型（autoboxing）并在需要时转换回来（auto-unboxing）。
相等性.两个对象相等意味着什么？如果我们用(a == b)测试相等性，其中a和b是相同类型的引用变量，我们正在测试它们是否具有相同的标识：是否引用相等。典型的客户端更希望能够测试数据类型值（对象状态）是否相同。每个 Java 类型都从Object继承了equals()方法。Java 为标准类型（如Integer、Double和String）以及更复杂类型（如java.io.File和java.net.URL）提供了自然的实现。当我们定义自己的数据类型时，我们需要重写equals()。Java 的约定是equals()必须是一个等价关系：

自反性: x.equals(x) 成立。
对称性: x.equals(y) 成立当且仅当 y.equals(x) 成立。
传递性: 如果 x.equals(y) 和 y.equals(z) 成立，则 x.equals(z) 也成立。

此外，它必须以 Object 作为参数，并满足以下属性。

一致性: 多次调用 x.equals(y) 一致地返回相同的值，前提是没有修改任何对象。
非空: x.equals(null) 返回 false。

遵循这些 Java 约定可能会有些棘手，就像 Date.java 和 Transaction.java 中所示的那样。
内存管理. Java 最重要的特性之一是其能够自动管理内存。当一个对象不再被引用时，它被称为孤立的。Java 跟踪孤立的对象，并将它们使用的内存返回给一个空闲内存池。以这种方式回收内存被称为垃圾回收。
不可变性. 一个不可变的数据类型具有一个特性，即对象的值在构造后永远不会改变。相比之下，可变的数据类型操作旨在改变的对象值。Java 为帮助强制实现不可变性提供了 final 修饰符。当你声明一个变量为 final 时，你承诺只能在初始化程序或构造函数中为其分配一个值。试图修改 final 变量的值的代码会导致编译时错误。
Vector.java 是一个用于向量的不可变数据类型。为了保证不可变性，它防御性地复制了可变的构造函数参数。
异常和错误是处理我们无法控制的意外错误的破坏性事件。我们已经遇到了以下异常和错误：

ArithmeticException。当发生异常的算术条件（例如整数除以零）时抛出。
ArrayIndexOutOfBoundsException。当使用非法索引访问数组时抛出。
NullPointerException。当需要对象而使用 null 时抛出。
OutOfMemoryError。当 Java 虚拟机无法分配对象因为内存不足时抛出。
StackOverflowError。当递归方法递归太深时抛出。

你也可以创建自己的异常。最简单的一种是终止程序执行并打印错误消息的 RuntimeException。

throw new RuntimeException("Error message here.");

断言是在我们开发的代码中验证我们所做假设的布尔表达式。如果表达式为 false，程序将终止并报告错误消息。例如，假设您有一个计算值，可能用于��引到数组中。如果这个值为负，它将在稍后引起ArrayIndexOutOfBoundsException。但如果您编写代码

assert index >= 0;

您可以确定发生错误的地方。默认情况下，断言是禁用的。您可以通过使用-enableassertions标志（简写为-ea）从命令行启用它们。断言用于调试：您的程序不应依赖断言进行正常操作，因为它们可能被禁用。

Q + A.

Q. Java 中是否有真正的不可变类？

如果使用反射，可以访问任何类的private字段并更改它们。程序 MutableString.java 演示了如何改变一个String。程序 MutableInteger.java 证明了即使实例变量是 final，这也是正确的。

练习

编写一个 Point2D.java 客户端，从命令行获取一个整数值 N，在单位正方形内生成 N 个随机点，并计算最近一对点之间的距离。
以下代码片段打印什么？

String string1 = "hello";
String string2 = string1;
string1 = "world";
StdOut.println(string1);
StdOut.println(string2);

解决方案：

world
hello

如果一个字符串 s 是字符串 t 的circular rotation，那么当字符被任意数量的位置循环移位时，它们匹配；例如，ACTGACG 是 TGACGAC 的循环移位，反之亦然。检测这种条件在基因组序列研究中很重要。编写一个程序，检查两个给定的字符串 s 和 t 是否彼此的循环移位。
解决方案： (s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)
以下递归函数返回什么？

public static String mystery(String s) {
    int N = s.length();
    if (N <= 1) return s;
    String a = s.substring(0, N/2);
    String b = s.substring(N/2, N);
    return mystery(b) + mystery(a);
}

解决方案： 字符串的反转。
使用我们的 Date.java 的实现作为模型，开发一个 Transaction.java 的实现。
使用我们在 Date.java 中的equals()的实现作为模型，为 Transaction.java 开发一个equals()的实现。

创意问题

有理数。 为有理数实现一个不可变的数据类型 Rational.java，支持加法、减法、乘法和除法。您不必担心溢出测试，但使用两个表示分子和分母的long值作为实例变量，以限制溢出的可能性。使用欧几里得算法确保分子和分母永远没有任何公因数。包括一个测试客户端，测试所有方法。
累加器的样本方差。 验证以下代码，为 Accumulator.java 添加var()和stddev()方法，计算作为addDataValue()参数呈现的数字的均值、样本方差和样本标准差。
参考： 这里有一个很好的解释这种一次性方法，最早由 Welford 在 1962 年发现。这种方法可以应用于计算偏度、峰度、回归系数和皮尔逊相关系数。
解析。 为您的 Date.java 和 Transaction.java 实现开发解析构造函数，使用下表中给出的格式的单个String参数指定初始化值。

1.3 袋子、队列和栈

原文：algs4.cs.princeton.edu/13stacks

译者：飞龙

协议：CC BY-NC-SA 4.0

几种基本数据类型涉及对象的集合。具体来说，值的集合是对象的集合，操作围绕向集合中添加、删除或检查对象展开。在本节中，我们考虑了三种这样的数据类型，称为袋子、队列和栈。它们在规定下一个要移除或检查的对象方面有所不同。

API。

我们为袋子、队列和栈定义了 API。除了基础知识外，这些 API 还反映了两个 Java 特性：泛型和可迭代集合。

泛型. 集合 ADT 的一个重要特征是我们应该能够将它们用于任何类型的数据。一种名为泛型的特定 Java 机制实现了这一功能。在我们的每个 API 中类名后面的表示将 Item 命名为 类型参数，一个用于客户端的具体类型的符号占位符。你可以将 Stack 理解为“项目的堆栈”。例如，你可以编写如下代码

Stack<String> stack = new Stack<String>();
stack.push("Test");
...
String next = stack.pop();

用于 String 对象的堆栈。
自动装箱. 类型参数必须实例化为引用类型，因此 Java 在赋值、方法参数和算术/逻辑表达式中自动在原始类型和其对应的包装类型之间转换。这种转换使我们能够在原始类型中使用泛型，就像以下代码中所示：

Stack<Integer> stack = new Stack<Integer>();
stack.push(17);        // autoboxing (int -> Integer)
int i = stack.pop();   // unboxing   (Integer -> int)

将基本类型自动转换为包装类型称为 自动装箱，将包装类型自动转换为基本类型称为拆箱。
可迭代集合. 对于许多应用程序，客户端的要求只是以某种方式处理每个项目，或者在集合中迭代。Java 的 foreach 语句支持这种范例。例如，假设 collection 是一个 Queue。那么，如果集合是可迭代的，客户端可以通过一条语句打印交易列表：

for (Transaction t : collection)
   StdOut.println(t);

袋子. 一个袋子是一个不支持移除项目的集合——它的目的是为客户提供收集项目并遍历收集项目的能力。Stats.java 是一个袋子客户端，从标准输入读取一系列实数，并打印出它们的平均值和标准差。
FIFO 队列. 一个 FIFO 队列 是基于 先进先出（FIFO）策略的集合。按照任务到达的顺序执行任务的策略在我们日常生活中经常遇到：从在剧院排队等候的人们，到在收费站排队等候的汽车，再到等待计算机应用程序服务的任务。
推入栈. 一个 推入栈 是基于 后进先出（LIFO）策略的集合。当你点击超链接时，浏览器会显示新页面（并将其推入栈）。你可以继续点击超链接访问新页面，但总是可以通过点击返回按钮重新访问上一页（从栈中弹出）。Reverse.java 是一个堆栈客户端，从标准输入读取一系列整数，并以相反顺序打印它们。
算术表达式求值.Evaluate.java 是一个堆栈客户端，用于评估完全括号化的算术表达式。它使用 Dijkstra 的 2 栈算法：

将操作数推送到操作数栈上。
将运算符推送到运算符栈上。
忽略左括号。
遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将将该运算符应用于这些操作数的结果推送到操作数栈上。

这段代码是一个 解释器 的简单示例。

数组和调整大小数组实现集合。

*固定容量的字符串栈。*FixedCapacityStackOfString.java 使用数组实现了一个固定容量的字符串栈。
*固定容量的通用栈。*FixedCapacityStack.java 实现了一个通用的固定容量栈。
数组调整大小栈。ResizingArrayStack.java 使用调整大小数组实现了一个通用栈。使用调整大小数组，我们动态调整数组的大小，使其足够大以容纳所有项目，同时又不会浪费过多空间。如果数组已满，在push()中我们将数组大小加倍；如果数组少于四分之一满，在pop()中我们将数组大小减半。
*数组调整大小队列。*调整大小数组队列.java 使用调整大小数组实现队列 API。

链表。

链表是一种递归数据结构，要么为空（null），要么是指向具有通用项和指向链表的节点的引用。要实现链表，我们从定义节点抽象的嵌套类开始。

private class Node {
   Item item;
   Node next;
}

构建链表。 要构建一个包含项目to、be和or的链表，我们为每个项目创建一个Node，将每个节点中的项目字段设置为所需值，并设置next字段以构建链表。
在开头插入。 在链表中插入新节点的最简单位置是在开头。
从开头删除。 删除链表中的第一个节点也很容易。
在末尾插入。 要在链表的末尾插入一个节点，我们需要维护一个指向链表中最后一个节点的链接。

遍历。 以下是遍历链表中节点的习惯用法。

for (Node x = first; x != null; x = x.next) {
   // process x.item
}

集合的链表实现。

*栈的链表实现。*Stack.java 使用链表实现了一个通用栈。它将栈作为一个链表维护，栈的顶部在开头，由实例变量first引用。要push()一个项目，我们将其添加到列表的开头；要pop()一个项目，我们将其从列表的开头移除。
队列的链表实现。 程序 Queue.java 使用链表实现了一个通用 FIFO 队列。它将队列作为一个链表维护，从最近添加的项目到最近添加的项目的顺序，队列的开始由实例变量first引用，队列的结束由实例变量last引用。要enqueue()一个项目，我们将其添加到列表的末尾；要dequeue()一个项目，我们将其从列表的开头移除。
背包的链表实现。 程序 Bag.java 使用链表实现了一个通用背包。该实现与 Stack.java 相同，只是将push()的名称更改为add()并删除pop()。

迭代。

要考虑实现迭代的任务，我们从一个客户端代码片段开始，该代码打印字符串集合中的所有项目，每行一个：

Stack<String> collection = new Stack<String>();
...
for (String s : collection)
   StdOut.println(s);
...

这个foreach语句是以下while语句的简写：

Iterator<String> i = collection.iterator();
while (i.hasNext()) { 
   String s = i.next();
   StdOut.println(s);
}

要在集合中实现迭代：

包含以下import语句，以便我们的代码可以引用 Java 的java.util.Iterator接口：

import java.util.Iterator;

将以下内容添加到类声明中，承诺提供一个iterator()方法，如Java.lang.Iterable接口中指定的：

implements Iterable<Item>

实现一个返回实现Iterator接口的类的对象的方法iterator()：

public Iterator<Item> iterator() {
    return new LinkedIterator();
}

实现一个嵌套类，通过包含hasNext()、next()和remove()方法来实现Iterator接口。我们总是对可选的remove()方法使用空方法，因为最好避免在迭代中插入修改数据结构的操作。

当底层数据结构是链表时，Bag.java 中的嵌套类LinkedIterator说明了如何实现一个实现Iterator接口的类。
当底层数据结构是数组时，ResizingArrayBag.java 中的嵌套类ArrayIterator也是如此。

自动装箱问题 + 回答

Q. 自动装箱如何处理以下代码片段？

Integer a = null;
int b = a;

A. 这导致运行时错误。原始类型可以存储其对应包装类型的每个值，除了null。

Q. 为什么第一组语句打印true，但第二组打印false？

Integer a1 = 100;
Integer a2 = 100;
System.out.println(a1 == a2);   // true
Integer b1 = new Integer(100);
Integer b2 = new Integer(100);
System.out.println(b1 == b2);   // false
Integer c1 = 150;
Integer c2 = 150;
System.out.println(c1 == c2);   // false

A. 第二个打印false，因为b1和b2是指向不同 Integer 对象的引用。第一个和第三个代码片段依赖于自动装箱。令人惊讶的是，第一个打印 true，因为在-128 和 127 之间的值似乎指向相同的不可变 Integer 对象（Java 的valueOf()实现在整数在此范围内时检索缓存值），而 Java 为此范围外的每个整数构造��对象。

这里是另一个 Autoboxing.java 的异常。

泛型问题 + 回答

Q. 泛型仅用于自动转换吗？

A. 不是，但我们只会用于“具体参数化类型”，其中每种数据类型都由单个类型参数化。主要好处是在编译时而不是运行时发现类型不匹配错误。泛型还有其他更一般（更复杂）的用途，包括通配符。这种一般性对于处理子类型和继承很有用。有关更多信息，请参阅这个泛型常见问题解答和这个Java 泛型教程。

Q. 具体参数化类型可以像普通类型一样使用吗？

A. 是的，有几个例外情况（数组创建、异常处理、使用instanceof和在类文字中）。

Q. 我可以将 Node 类设为静态吗？

A. 对于 LinkedStackOfString.java，你可以这样做而不需要其他更改，并节省每个节点的 8 字节（内部类开销）。然而，在 LinkedStack.java 中的嵌套类Node使用外部类的Item类型信息，因此你需要做一些额外的工作使其静态化。Stack.java 通过使嵌套类（和嵌套迭代器）泛型化来实现这一点：有三个单独的泛型类型参数，每个都命名为Item。

Q. 当我尝试创建泛型数组时为什么会出现“无法创建泛型数组”的错误？

public class ResizingArrayStack<Item> {
   Item[] a = new Item[1];

A. 不幸的是，在 Java 1.5 中无法创建泛型数组。根本原因是 Java 中的数组是协变的，但泛型不是。换句话说，String[]是Object[]的子类型，但Stack不是Stack的子类型。为了解决这个缺陷，你需要执行一个未经检查的转换，就像在 ResizingArrayStack.java 中一样。ResizingArrayStackWithReflection.java 是一个（笨拙的）替代方案，通过使用反射来避免未经检查的转换。

Q. 那么，为什么数组是协变的？

A. 许多程序员（和编程语言理论家）认为 Java 类型系统中的协变数组是一个严重的缺陷：它们会产生不必要的运行时性能开销（例如，参见ArrayStoreException），并且可能导致微妙的错误。Java 引入协变数组是为了解决 Java 最初设计中不包含泛型的问题，例如，实现Arrays.sort(Comparable[])并使其能够接受String[]类型的输入数组。

Q. 我可以创建并返回一个参数化类型的新数组吗，例如为泛型队列实现一个toArray()方法？

A. 不容易。你可以使用反射来实现，前提是客户端向toArray()传递所需具体类型的对象。这是 Java 集合框架采取的（笨拙的）方法。GenericArrayFactory.java 提供了一个客户端传递Class类型变量的替代解决方案。另请参阅 Neal Gafter 的博客，了解使用type tokens的解决方案。

`迭代器问答`

Q. 为什么这个结构被称为foreach，而它使用关键字for？

A. 其他语言使用关键字foreach，但 Java 开发人员不想引入新关键字并破坏向后兼容性。

Q. String可迭代吗？

A. 不。

Q. 数组是Iterable吗？

A. 不。你可以使用它们的 foreach 语法。但是，你不能将数组传递给期望Iterable的方法，也不能从返回Iterable的方法返回数组。这样会很方便，但实际上不起作用。

Q. 以下代码片段有什么问题？

String s;
for (s : listOfStrings)
   System.out.println(s);

A. 增强的 for 循环要求在循环内部声明迭代变量。

`练习`

在 FixedCapacityStackOfStrings.java 中添加一个isFull()方法。
给出java Stack对输入打印的输出

it was - the best - of times - - - it was - the - -

解决方案。was best times of the was the it (1 left on stack)
假设执行了一系列交错的（栈）push和pop操作。push 操作按顺序将整数 0 到 9 推入栈；pop 操作打印返回值。以下哪种序列不可能发生？

(a)  4 3 2 1 0 9 8 7 6 5
(b)  4 6 8 7 5 3 2 9 0 1
(c)  2 5 6 7 4 8 9 3 1 0
(d)  4 3 2 1 0 5 6 7 8 9
(e)  1 2 3 4 5 6 9 8 7 0
(f)  0 4 6 5 3 8 1 7 2 9
(g)  1 4 7 9 8 6 5 3 0 2
(h)  2 1 4 3 6 5 8 7 9 0

答案：(b)、(f)和(g)。
编写一个栈客户端 Parentheses.java，从标准输入中读取一系列左右括号、大括号和方括号，并使用栈来确定序列是否平衡。例如，你的程序应该对[()]{}{[()()]()}打印true，对[(])打印false。
当n为 50 时，以下代码片段打印什么？给出当给定正整数n时它的高级描述。

Stack<Integer> s = new Stack<Integer>();
while (n > 0) {
   s.push(n % 2);
   n = n / 2;
}
while (!s.isEmpty())
    System.out.print(s.pop());
System.out.println();

答案：打印N的二进制表示（当n为50时为110010）。
以下代码片段对队列q做了什么？

Stack<String> s = new Stack<String>();
while(!q.isEmpty())
   s.push(q.dequeue());
while(!s.isEmpty())
   q.enqueue(s.pop());

答案：颠倒队列中的项目。
在 Stack.java 中添加一个peek方法，返回栈中最近插入的项（不弹出）。
编写一个过滤器程序 InfixToPostfix.java，将中缀算术表达式转换为后缀表达式。
编写一个程序 EvaluatePostfix.java，从标准输入中获取后缀表达式，对其进行评估，并打印值。（将上一个练习的程序输出通过管道传递给这个程序，可以实现与 Evaluate.java 相同的行为。）
假设客户端执行了一系列交错的（队列）enqueue和dequeue操作。enqueue 操作按顺序将整数 0 到 9 放入队列；dequeue 操作打印返回值。以下哪种序列不可能发生？

(a)  0 1 2 3 4 5 6 7 8 9
(b)  4 6 8 7 5 3 2 9 0 1 
(c)  2 5 6 7 4 8 9 3 1 0
(d)  4 3 2 1 0 5 6 7 8 9

开发一��类 ResizingArrayQueueOfStrings，使用固定大小数组实现队列抽象，然后扩展您的实现以使用数组调整大小以消除大小限制。解决方案: ResizingArrayQueue.java

`链表练习`

`创意问题`

约瑟夫问题。在古代的约瑟夫问题中，N 个人陷入困境，并同意采取以下策略来减少人口。他们围成一个圆圈（位置从 0 到 N-1 编号），沿着圆圈进行，每隔 M 个人就淘汰一个，直到只剩下一个人。传说中约瑟夫找到了一个位置可以避免被淘汰。编写一个 Queue 客户端 Josephus.java，从命令行获取 M 和 N，并打印出人们被淘汰的顺序（从而向约瑟夫展示在圆圈中应该坐在哪里）。

% java Josephus 2 7
1 3 5 0 4 2 6

普林斯顿算法讲义（一）（3）https://developer.aliyun.com/article/1484169

普林斯顿算法讲义（一）(2)