API介绍
背包
public class Bag<Item> implements Iterable<Item>
{
Bag() // 创建一个空背包
void add(Item item) // 向背包中添加一个元素
boolean isEmpty() // 背包是否为空
int size() // 背包中的元素数量
}
队列
public class Queue<Item> implements Iterable<Item>
{
Queue() // 创建空队列
void enqueue(Item item) // 添加一个元素
Item dequeue() // 删除最早添加的元素
boolean isEmpty() // 队列是否为空
int size() // 队列中的元素数量
}
栈
public class Stack<Item> implements Iterable<Item>
{
Stack() // 创建一个空栈
void push(Item item) // 压入一个元素
Item pop() // 推出最后压入的元素
boolean isEmpty() // 栈是否为空
int size() // 栈中的元素数量
}
特点及用例
背包
- 不支持从中删除元素
- 迭代的顺序不确定且与用例无关
// 用于计算平均数和标准差
public class Stats
{
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.printf("Mean: %.2f\n", mean);
StdOut.printf("Std: %.2f\n", std);
}
}
队列
- 先进先出（FIFO）
- 入列顺序和出列顺序相同
// 将队列的中数字拷贝到数组当中
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(); // FIFO: 顺序保持不变
return a;
}
栈
- 后进先出（LIFO）
- 可是使用双栈来求解数学运算
public class Evaluate
{
public static void main(String[] args)
{
Stack<String> ops = new Stack<String>(); // 操作符栈
Stack<Double> vals = new Stack<Double>(); // 操作数栈
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(")"))
{
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;
vals.push(v);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
集合类数据类型的实现
动态变容量的栈(数组实现)
- 需要resize方法动态扩展栈的容量
- push的时候，需要检查栈和数组的大小，合适的时候进行扩容
- pop的时候，当栈的大小小于数组的1/4的时候，数组缩减为原来的1/2
- pop的时候，将不使用的对象置为null，方便垃圾回收
- 实现iterable接口，方便遍历
import java.util.Iterator
public class ResizeingArrayStack<Item> implements Iterable<Item> {
private Item[] a = (Item[]) new Object[1]; // 栈元素
private int N = 0; // 元素数量
public boolean isEmpty() {return N == 0;}
public int size() {return N;}
private void resize(int max) {
// 将一个数组移动到一个新的数组当中
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}
public void push(Item item) {
if (N == a.length) {resize(2 * a.length)}
a[N++] = item;
}
public Item pop() {
Item item = a[--N];
a[N] = null;// 避免对象游离
if (N > 0 &&N < a.length / 4)
resize(a.length / 2);
}
public Iterator<Item> iterator() {
return new ReverseArrayIterator()
}
private class ReverseArrayIterator implements Iterator<Item>{
// 实现后进先出的迭代顺序
private int i = N;
public boolean hasNext() { return N > 0; }
public Item next() { return a[--i]; }
public void remove() {}
}
}
动态变容量的栈(链表实现)
import java.util.Iterator
public class Stack<Item> implements Iterable<Item> {
private Node first;
private int N;
private class Node {
Item item;
Node next;
}
public boolean isEmpty(){
return N == 0;
}
public int size() {
return N;
}
public void push(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
public Item pop() {
Item item = first.item;
first = first.next;
N--;
return item;
}
}
动态变容量的队列(链表实现)
由于实现队列需要使用两个指针（first/last）， 所以需要考虑一些特殊情况。
- 入队列的时候，如果只有一个元素，需要将first和last都指向第一个元素
- 出队列的时候，如果是最后一个元素，需要将last置为null
import java.util.Iterator
public class Queue<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int N;
private class Node {
Item item;
Node next;
}
public boolean isEmpty(){
return N == 0;
}
public int size() {
return N;
}
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty())
first = last;
else
oldLast.next = last;
N++;
}
public Item dequeue() {
Item item = first.item;
first = first.next;
if(isEmpty())
last = null;
N--;
return item;
}
}
