算法第四版学习笔记–1.3 Bags, Queues and Stacks

前面120页都是Java基础，建议有Java基础的同学可以直接从120页开始学习，但是这里面的例子有用到algs4这个jar，需要稍微了解一下，影响不大，都是对JDK的一些封装。

Introduction

这一章，包括bag, queue, 和 stack。都是用来存东西，都有add，remove，examine，但是呢，他们有着一些区别，（哪一个对象是下一次remove或者examine）。
三个目标：

强调数据结构对效率的影响
介绍泛型和迭代器
介绍linked data structure，（linked list）可以用来实现以上提到的三种数据结构

API

Bag

public class Bag<Item> implements Iterable<Item>Bag() //无参构造方法void add(Item item) //添加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 dev: %.2f\n", std);
}
}

FIFO Queue 先进先出

public class Queue<Item> implements Iterable<Item>Queue()void enqueue<Item> // 加一个Item dequeue() //removeboolean isEmpty()int size()

队列遵循先进先出政策。
在这里插入图片描述
典型的使用队列的例子，把对象存放在一个集合中，并且要保持他们的相对顺序。

PushDown (LIFO) Stack 后进先出

public class Stack<Item> implements Iterable<Item>Stack()void push(Item item) //addItem pop() //remove 最新加入的boolean isEmpty()int size()

栈是一种基于后进先出规则的一种集合。
什么时候需要用到它，反向输出的时候！！！！！
在这里插入图片描述
泛型，自动开箱，自动装箱。。。就不细说了。。。

算数表达式evaluation

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
假设：

可以是一个数字，一个左括号跟一个算数表达式一个操作符另一个算数表达式右括号。（expression 操作符 expression）可以嵌套。
我们只考虑全括号状态，只靠括号来判断，而不是依靠优先级
只有 + - * / sqrt

public class Evaluate {public static void main(String[] args) {char[] c = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )".toCharArray();String op = "+-*/";Stack<String> ops = new Stack<String>();Stack<Double> vals = new Stack<Double>();for (char cc : c) {if (cc == ' ' || cc == '(') {//do nothing} else if (op.contains(String.valueOf(cc))) {ops.push(String.valueOf(cc));} else if (cc == ')') {double a = vals.pop();double b = vals.pop();double result = 0.0;switch (ops.pop()){case "+":result = a+b;break;case "-":result = a-b;break;case "*":result = a*b;break;case "/":result = a/b;break;}vals.push(result);} else {vals.push(Double.valueOf(String.valueOf(cc)));}}System.out.println(vals.pop());}
}