1.3背包,队列和占道

1.3.1API

1.3.1.3可迭代的集合类型

如果集合是可迭代的,就能够使用foreach语句

1.3.1.4背包

背包(Bag)是一种不支持从中删除元素的集合类型

1.3.1.5先进先出队列*

队列(Queue)是一种基于先进先出(FIFO)的集合类型

使用情形: 在集合保存元素的同时保存相对顺序:使它们入列顺序和出列顺序相同

1.3.1.6下压栈*

栈(Stack)是一种基于后进先出(LIFO)的集合类型

使用情形: 在集合保存元素的同时颠倒相对顺序

1.3.1.7算术表达式求值*

求值算法:双栈运算法

操作:

  1. 准备两个栈:运算符栈,操作数栈
  2. 忽略左括号,将操作数和运算符分别压入对应栈内
  3. 遇到右括号,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的结果压入操作数栈

漏洞:

  1. 最多只能有两个操作数在括号内运算
  2. 必须有左括号和右括号

1.3.2集合类数据类型的实现

1.3.2.2 泛型*

创建泛型数组在Java中不被允许,需要使用强转

  1. Item[] a = (Item[]) new Object[cap];

1.3.2.4对象游离*

栈中元素pop()后,被弹出元素的引用依旧存在于数组中,但元素不会再被访问,垃圾回收机无法判断,除非引用被覆盖,这是需要使引用指向null

  1. Item item = a[--N];
  2. a[N] = null;//防止游离

1.3.2.5迭代*

实现可迭代类的方法:

  1. 集合实现Iterable接口,在类中重写iterator()方法,并返回迭代器Iterator
  1. implements Iterable<Item> 
  3. public Iterator<Item> iterator(){
  4.     return new XXXIterator();
  5. }
  1. 根据不同要求,可以编写子类XXXIterator,重写hasNext(),next(),remove()方法,生成迭代器

1.3.3 链表*

链表定义:一种递归的数据结构,或者为空(null),或者指向一个节点(node)的引用,该结点含有一个泛型元素和一个指向另一条链表的引用.

1.3.3.1节点记录
  1. private class Node{
  2.     Item item;
  3.     Node mext;
  4. }

1.3.3.7遍历
  1. for(Node x = first; x != null; x = x.next){
  2.     //链表的遍历
  3. }

1.3.4综述

基础数据结构
数据结构 优点 缺点
数组 通过所以可直接访问任意元素 在初始化时就需知道元素数量
链表 使用的空间大小和元素数量成正比 需通过引用访问任意元素

答疑

1.为什么将内部类Node声明为private?

为了将Node的方法和实例变量的访问范围限制在包含它的类中.私有嵌套类的特点:只有包含它的类可以直接访问它的实例变量,所以无需声明它的实例变量为public或private

2. 为什么不实现一个单独的Collection数据类型实现添加,删除,迭代?

宽接口无法保证高效的实现某些方法,设计只有几个操作的借口可以简化操作,并限制用例行为.