書中例題
Bag背包
背包是一種不支持從中刪除元素的集合數(shù)據(jù)類型——它的目的就是幫助用例收集元素并迭代遍歷收集到的元素。迭代的順序不確定且與用例無關(guān)。
以下代碼框列出的是常用背包用例。
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
/**
* 簡單計(jì)算標(biāo)準(zhǔn)輸入中的所有double值的平均值和樣本標(biāo)準(zhǔn)差.
* 平均值為它們的和除以N;
* 樣本標(biāo)準(zhǔn)差為每個(gè)值和平均值之差的平方之和除以N-1之后的平方根
* @author Zoye
*
*/
public class Status {
public static void main(String[] args) {
Bag<Double> numbers = new Bag<Double>();
while(!StdIn.isEmpty()) {
numbers.add(StdIn.readDouble());
}
int N = numbers.size();
double sum = 0.0;
for (Double x : numbers) {
sum += x;
}
double mean = sum/N;
sum = 0.0;
for (Double x : numbers) {
sum += (x-mean)*(x-mean);
}
double std = Math.sqrt(sum/(N-1));
StdOut.println("mean:"+mean);
StdOut.println("std:"+std);
}
}
Queue隊(duì)列
隊(duì)列是一種先進(jìn)先出（FIFO）的集合類型。在應(yīng)用程序中使用隊(duì)列的主要原因是在用集合保存元素的同時(shí)保存它們的相對順序：使它們?nèi)肓许樞蚝统隽许樞蛳嗤?/p>
例如，以下用例是In類的靜態(tài)方法readInts()的一種實(shí)現(xiàn)。這個(gè)方法為用例解決的問題是用例無需預(yù)先知道文件的大小即可將文件中的所有整數(shù)讀入一個(gè)數(shù)組中。
public static int[] readInts(String name) {
In in = new In(name);
Queue<Integer> q = new Queue<Integer>();
while(!in.isEmpty()) {
q.enqueue(in.readInt());
}
int N = q.size();
int[] a = new int[N];
for(int i = 0 ; i < N ; i++ ) {
a[i] = q.dequeue();
}
return a;
}
Stack棧
棧是一種后進(jìn)先出（LIFO）的集合類型。
以下為其中一典型用例。
/**
* 把標(biāo)準(zhǔn)輸入中的所有證書逆序排列,無需預(yù)先知道整數(shù)的多少
* @author Zoye
*
*/
public class Reverse {
public static void main(String[] args) {
Stack<Integer> stack;
stack = new Stack<Integer>();
while(!StdIn.isEmpty()){
stack.push(StdIn.readInt());
}
while(!stack.isEmpty()){
StdOut.println(stack.pop());
}
//錯(cuò)誤的遍歷方式,對于java.util.Stack
//對于edu.princeton.cs.algs4.Stack則是正確的
// for (int i : stack) {
// StdOut.println(i);
// }
}
}
算術(shù)表達(dá)式求值
既是棧用例也是展示泛型的應(yīng)用的一個(gè)典型例子。
表達(dá)式由括號、運(yùn)算符和操作數(shù)（數(shù)字）組成。我們根據(jù)以下4種情況從左到右逐個(gè)將這些實(shí)體送入棧處理：
- 將操作數(shù)壓入操作數(shù)棧；
- 將運(yùn)算符壓入運(yùn)算符棧；
- 忽略左括號；
- 在遇到右括號時(shí)，彈出一個(gè)運(yùn)算符，彈出所需數(shù)量的運(yùn)算數(shù)，并將運(yùn)算符和操作數(shù)的運(yùn)算結(jié)果壓入操作數(shù)棧。
以下為該算法的一個(gè)實(shí)現(xiàn)。
package chapter3;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
/**
* 解釋給定字符串所表達(dá)的運(yùn)算并計(jì)算得到結(jié)果
* @author Zoye
*
*/
public class Evaluate {
public static void main(String[] args) {
//兩個(gè)棧,一個(gè)操作數(shù)棧,一個(gè)運(yùn)算符棧
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
//讀取字符,如果是運(yùn)算符就入棧
while(!StdIn.isEmpty()){
String s = StdIn.readString();
if(s.equals("(")) ;
else if(s.equals("+")) ops.push(s);
else if(s.equals("-")) ops.push(s);
else if(s.equals("*")) ops.push(s);
else if(s.equals("/")) ops.push(s);
else if(s.equals("sqrt")) ops.push(s);
else if(s.equals(")")) {
//如果字符為")",彈出運(yùn)算符和操作數(shù),計(jì)算結(jié)果并壓入棧
String op = ops.pop();
double v = vals.pop();
if(op.equals("+")) v = vals.pop() + v;
else if(op.equals("-")) v = vals.pop() - v;
else if(op.equals("-")) v = vals.pop() - v;
else if(op.equals("*")) v = vals.pop() * v;
else if(op.equals("/")) v = vals.pop() / v;
else if(op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} else{
//如果字符既非運(yùn)算符也不是括號,將它作為double值壓入棧
vals.push(Double.parseDouble(s));
}
}
StdOut.println(vals.pop());
}
}
