数据结构与算法复习（一）

数据结构 , , 评论

本篇为复习数据结构与算法的第一篇

背包、队列和栈

API

  • 泛型可迭代的基础集合数据类型的API
背包 public class Bag<Item> implements Iterable<Item>
Bag() 创建一个空背包
void add(Item item) 添加一个元素
boolean isEmpty() 背包是否为空
int size() 背包中的元素数量
先进先出(FIFO)队列 public class Queue<Item> implements Iterable<Item>
Queue() 创建空队列
void enqueue(Item item) 添加一个元素
Item dequeue() 删除最早添加的元素
boolean isEmpty() 队列是否为空
int size() 队列中的元素数量
下压(后进先出，LIFO)栈 public class Stack<Item> implements Iterable<Item>
Stack() 创建一个空栈
void push(Item item) 添加一个元素
Item pop() 删除最近添加的元素
boolean isEmpty() 栈是否为空
int size() 栈中的元素数量
  1. 泛型
  • 集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java机制能够做到这一点，它被成为泛型，也叫做参数化类型。
  • 在每份API中，类名后的记号将Item定义为一个类型参数，它一个象征性的占位符，表示的是用例将会使用的某种具体数据类型。可以将Stack理解为某种元素的栈。
  • 在创建栈时，用例会提供一种具体的数据类型：我们可以将Item替换为任意引用数据类型（Item出现的每个地方都是如此）。
  1. 自动装箱
  • 类型参数必须被实例化为引用类型，因此Java有一种特殊机制来使泛型代码能够处理原始数据类型。
    1
    2
    3
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(17);   //自动装箱(int -> Integer)
    int i = stack.pop();  //自动拆箱(Integer -> int)
  • 自动将一个原始数据类型转换为一个封装类型被成为自动装箱，自动将一个封装类型转换为一个原始数据类型被成为自动拆箱。
  1. 可迭代的集合类型
  • 对于许多应用场景，用例的要求只是用某种方式处理集合中的每个元素，或者叫做迭代访问集合中的所有元素。
  • 例如，假设用例在Queue中维护一个交易集合：
1
2
3
4
5
6
Queue<Transaction> collection = new Queue<Transaction>();
//如果集合是可迭代的，用例用一行语句即可打印出交易的列表：
for(Transaction t : collection){
    StdOUt.println(t);
}
//这种语法叫做foreach语句：可以将for语句看做对于集合中的每个交易t(foreach)，执行一下代码断。
  1. 背包
  • 背包市一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例手机元素并迭代便利所有收集到的元素（用例也可以检查背包是否为空或者获取背包中的元素数量）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 dev: %.2f\n", std);
    }
}
  • 上述的Stats类是Bag的一个典型用例。它的任务是简单的计算标准输入中的所有double值的平均值和样本标准差。如果标准输入中有N个数字，那么平均值为它们的和除以N，样本标准差为每个值和平均值只差的平方之和除以N-1之后的平方根。
  • 在这些计算中，数的计算顺序和结果无关，因此我们将它们保存在一个Bag对象中并使用foreach语法来计算每个和。
  • **注意:**不需要保存所有的数也可以计算标准差（就像我们在Accumulator中计算平均值那样）。
  1. 先进先出队列
  • 先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。
  • 在提到公平时大多数热的第一个想法就是应该优先服务等待时间最久的人，这正是先进先出策略的准则。队列是许多日常现象的自然模型，它是无数应用程序的核心。
  • 当用例使用foreach语句迭代访问队列中的元素时，元素的处理顺序就是它们被添加到队列中的顺序。
  1. 下压栈
  • 下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。
  • 当你的邮件在桌上放成一叠时，使用的就是栈。
  • 这种策略的好处是我们能够及时看到感兴趣的邮件，坏处是如果你不把栈清空，某些较早的邮件可能永远不会被阅读。
  • 当用例使用foreach语句迭代遍历栈中的元素时，元素处理顺序和它们被压入栈的顺序正好相反。
  • 在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒他们的相对顺序。
1
2
3
4
5
6
7
8
9
10
public class Reserse{
    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);
    }
}
  1. 算术表达式求值
  • E.W.Dijkstra在20世纪60年代发明了一个非常简单的算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务，其实现过程如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//Dijkstra的双栈算术表达式求值算法
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("sqrt"))   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;
                else if (op.equals("sqrt"))     v = Math.sqrt(v);
                vals.push(v);
            }   //如果字符既非运算符也不是括号，将它作为double值压入栈
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}
  • 这段Stack的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。有了泛型，我们只需实现Stack一次即可使用String值的栈和Double值的栈。
  • 表达式由括号、运算符和操作数（数组）组成。我们根据一下4种情况从左到右逐个将这些实体送入栈处理：
    1. 将操作数压入操作数栈；
    2. 将运算符压入运算符栈；
    3. 忽略左括号；
    4. 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈中。

未完待续……

希川Engineer

格物致知。