海创软件组-20200712-背包,队列和栈-算法4
程序员文章站
2022-06-01 08:49:39
...
三种数据类型:背包(Bag),队列(Queue)和栈(Stack).他们的不同在于删除和访问对象的顺序不同
目标
- 说明我们对集合中的对象的表示方式将直接影响各种操作的效率
- 介绍泛型和迭代
- 说明链式数据结构的重要性
API
每份API都含有一个无参数的构造函数,一个向集合中添加单个元素的方法,一个测试集合是否是空的方法和一个返回集合大小的方法.Stack和Queue都含有一个能够删除集合中特定的元素的方法.
泛型
集合类的一个抽象数据类型的一个关键特性是我们应该可以用他们来存储任意类型的数据.一个特殊的Java机制可以做到这一点,他被称为泛型,也叫作参数化类型
自动装箱
类型参数必须被实例化为引用类型.因为Java有一种特殊机制来使得泛型代码能够处理原始数据类型.我们记得Java的封装类型都是原始数据类型所对应的引用类型:
Boolean,Byte,Character,Double,Float,Integer,Long,Short分别对应着boolean,byte,char,double,float,int,long,short
在处理赋值语句,方法的参数和算数或逻辑表达式时,Java会自动在引用类型和对应的原始类型之间进行转换.在这里,这种转换有益于我们同时使用泛型和原始数据类型
Stack<Integer> stack = new Stack<>();
stack.push(17); //自动装箱(int ->Integer)
int i = stack.pop();//自动拆箱(Integer->int)
- 自动装箱:自动将一个原始数据类型转换为一个封装数据类型成为自动装箱
- 自动拆箱:自动将一个封装类型转换为一个原始数据类型被称为自动拆箱
可迭代的集合元素
对于许多应用场景,用例的要求只是用某种方式处理集合中的每个元素,或者叫做迭代访问集合中的所有元素
假设在Queue中维护一个交易集合,如下:
Queue<Transaction> collection = new Queue<>();
如果集合是可迭代的,用一句话即可打印出集合的列表
for(Transaction t : collection){
System.out.println(t);
}
这种语句叫做foreach语句
背包
背包是一种不支持从中删除元素的集合数据类型-他的目的就是帮助用例收集元素并迭代遍历所有收集到的元素数量(用例也可以检查背包是否为空或者获取背包中元素的数量)
package 基础.背包队列栈;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* 定义泛型背包类
*/
public class Bag<Item> implements Iterable<Item> {
//泛型元素链表
private Node<Item> first;
//元素数量
private int n;
//当前链表指向的元素
private Node<Item> curr;
/**
* 创建一个控背包
*/
public Bag() {
curr=first;
}
/**
* 添加一个元素
* @param item
*/
public void add(Item item){
Node<Item> oldFirst = first;
Node<Item> first = new Node<>();
first.var=item;
first.next=oldFirst;
this.first=first;
n++;
}
/**
* 背包是否为空
* @return
*/
public boolean isEmpty(){
return first==null;
}
// public Iterator iterator(){
// return (Iterator) new ListIterator<Item>(first);
// }
/**
* 背包中元素的数量
* @return
*/
public int size(){
return n;
}
/**
* 实现一个迭代器
* @return
*/
@Override
public Iterator<Item> iterator() {
return new ListIterator<>(first);
}
/**
* 具体迭代器实现
* @param <Item>
*/
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
/**
* 使用背包的链表子元素
* @param first
*/
public ListIterator(Node<Item> first) {
this.current = first;
}
/**
* 链表是否为空
* @return
*/
public boolean hasNext() {
return current != null;
}
public void remove(){
throw new UnsupportedOperationException();
}
/**
* 当前链表的下一个元素
* @return
*/
public Item next() {
if (!hasNext()){
throw new NoSuchElementException();
}
Item item = current.var;
current=current.next;
return item;
}
}
/**
* 一个简单的链表
* @param <Item>
*/
class Node<Item>{
private Item var;
private Node next;
public Node(Item var) {
this.var = var;
}
public Node() {
}
}
}
package 基础.背包队列栈;
import java.util.Scanner;
/**
* 求平均值和标准差
*/
public class Stats {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Bag<Double> numbers = new Bag<>();
//终止pattern是0;类型是ctrl+z
while (!in.hasNext("0")){
numbers.add(in.nextDouble());
}
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);
}
//N-1是因为计算精度更高
double std = Math.sqrt(sum/(N-1));
System.out.println("Mean: "+String.format("%.2f",mean));
System.out.println("Std dev: "+String.format("%.2f",std));
}
}
先进先出队列
先进先出队列(简称队列)是一种基于先进先出(FIFO)策略的集合类型
API实现
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 先进先出队列
* @param <Item>
*/
public class Queue<Item> implements Iterable<Item> {
//双链表队列
private Node<Item> first;
private Node<Item> last;
private int n;
/**
* 添加一个元素
* @param item
*/
public void enqueue(Item item){
Node<Item> oldLast = last;
last.var=item;
last.next=null;
if (isEmpty()){
first = last;
}else{
oldLast.next=last;
}
n++;
}
public int size(){
return n;
}
/**
* 删除表头元素
*/
public Item dequeue(){
if (isEmpty()){
throw new NoSuchElementException();
}
Item item = first.var;
if (first.next != null){
first=first.next;
}else{
first=last=null;
}
n--;
return item;
}
/**
* 空构造函数
*/
public Queue() {
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return first == null;
}
/**
* 迭代器
* @return
*/
@Override
public Iterator<Item> iterator() {
return new QueueStack(first);
}
private class QueueStack implements Iterator<Item>{
private Node<Item> current;
public QueueStack(Node<Item> first) {
this.current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if (!hasNext()){
throw new NoSuchElementException();
}
Item item = current.var;
current=current.next;
return item;
}
}
}
/**
* 先进先出
* @param name
* @return
* @throws InterruptedException
*/
public static int[] readInts(String name) throws InterruptedException {
Scanner in = new Scanner(System.in);
Queue<Integer> q = new Queue<>();
int N = 0;
while (!in.hasNext("EOF")){
q.enqueue(in.nextInt());
N++;
}
int [] a = new int[N];
for (int i = 0; i < N; i ++){
a[i] = q.dequeue();
}
return a;
}
下压栈
下压栈(或者简称栈)是一种基于后进先出(LIFO)策略的集合类型
- 下压栈数据类型实现
package 基础.背包队列栈;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 下压栈
* @param <Item>
*/
public class Stack<Item> implements Iterable<Item> {
//下压栈栈顶
private Node<Item> first;
//元素数量
private int n;
/**
* 空构造函数
*/
public Stack() {
}
/**
* 添加一个元素
* @param item
*/
public void push(Item item){
Node<Item> oldFirst = first;
first = new Node<>();
first.var=item;
first.next=oldFirst;
n++;
}
/**
* 删除最近添加的元素
* @return
*/
public Item pop(){
if (first == null){
throw new NoSuchElementException();
}
Item item = first.var;
if (first.next == null){
first= null;
}else{
first=first.next;
}
n--;
return item;
}
/**
* 栈是否为空
* @return
*/
public boolean isEmpty(){
return first==null;
}
/**
* 栈中元素数量
* @return
*/
public int size(){
return n;
}
@Override
public Iterator<Item> iterator() {
return new StackIterator(first);
}
private class StackIterator implements Iterator<Item>{
private Node<Item> current;
public StackIterator(Node<Item> first) {
this.current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if (!hasNext()){
throw new NoSuchElementException();
}
Item item = current.var;
current = current.next;
return item;
}
}
}
import java.util.Scanner;
public class Reverse {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Stack<Integer> stack;
stack = new Stack<>();
while (!in.hasNext("EOF")){
stack.push(in.nextInt());
}
while (!stack.empty()){
System.out.println(stack.pop());
}
}
}
算数表达式求值
我们要学习的另一个栈的用例同时也是展示泛型应用的一个经典例子.就是计算算术表达式的值,例如(1+((2+3)(45))).
如果将4乘以5,把3加上2,取他们的乘积然后加上1,就得到了101.
表达式由括号,运算符和操作数(数字)组成.我们根据一下四种情况从左到右逐个将这些实体送入栈处理:
- 将操作数压入操作数栈
- 将运算符压入运算符栈
- 忽略左括号
- 在遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的运算结果压入操作数栈
在处理完成最后边的那个括号之后,操作数栈上只会有一个值,他就是表达式的值.
package 基础.背包队列栈;
import java.util.Scanner;
import java.util.Stack;
/**
* Dijkstra的双栈算术表达式求值算法
*/
public class Evaluate {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
while (!in.hasNext("EOF")){
//读取字符,如果是运算符则压入栈
String s = in.next();
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);
}
//如果字符既非运算符也非括号,将他作为dpuble值压入栈
else {
vals.push(Double.valueOf(s));
}
}
//最终答案
System.out.println(vals.pop());
}
}
迭代
集合类数据类型的基本操作之一就是,能够使用Java的foreach语句通过迭代遍历处理集合中的每个元素.这种方式的代码即清晰又简洁,且不依赖集合数据类型的具体实现.在讨论迭代的实现之前我们先看一段能够打印出一个字符串集合中的所有元素的用例代码:
Stack<String> collection = new Stack<>();
for(String s : collection){
System.out.println(s);
这里的foreach语句是while语句的一种简写方式(就好像for语句一样).他本质上和while语句是等价的:
Iterator<String> i = collection.iterator();
while(iterator.hasNext()){
String s = iterator.next();
System.out.println(s);
}
这段代码为我们展示了一些可以在任意可迭代的集合数据类型中我们需要实现的东西
**- 集合数据类型必须实现一个iterator()方法并返回一个Iterator对象
- Iterator类必须包含两个方法:hasNext()(返回一个布尔值)和next()(返回集合中的一个泛型元素)**
在Java中我们使用接口机制指定一个类实现所必须实现的方法.对于可迭代的集合数据类型,Java已经为我们定义了所需要的接口.要使得的一个类可迭代,
- 第一步就是在他的声明中加入implements Iterable,对应的接口(即java.lang.Iterable)为:
public interface Iterable{
Iterator iterator();
} - 然后在类中添加一个方法iterator()并返回一个迭代器Iterator.迭代器都是泛型的,因此我们可以使用参数Item来帮助遍历他们指定的任意类型的对象.对于一直使用的数组表示法,我们需要逆序迭代遍历这个数组,因此我们将迭代器命名为ReverseArrayIterator,并添加一下方法
public Iterator<Item> iterator(){
return new ReverseArrayIterator();
}
迭代器是什么?他是一个实现了hasNext()和Next()方法的类的对象,由一下接口定义,即java.lang.Iterator
public interface Iterator<Item>{
boolean hasNext();
Item next();
void remove();
}
尽管接口中定义了一个remove方法,但是本书中remove()方法总是空,因此我们希望避免在迭代中穿插能够修改数据结构的操作.对于ReverseArrayIterator,这些方法都只需要一行代码,他们实现在栈类中的一个嵌套类中:
private class ReverseArrayIterator implements Iterator<Item>{
private int =N;
public bolean hasNext(){ return i > 0;}
public Item next() {return }
}
请注意,嵌套类可以访问包含他的类的实例变量,在这里就是a[]和N(这也是我们使用嵌套类实现迭代器的主要原因).
从技术角度来说,为了和Iterator的结构保持一致,我们应该在两种情况下跑出异常;如果用例调用了remove()则抛出UnsupportedOperationException,如果用例在调用next()时i为0则抛出NoSuchElementException .因为我们只会在foreach语法中使用迭代器,这些情况都不会出现,所以我们省略了这部分代码.还有一个非常重要的细节我们需要在开头加上这条语句:
import java.util.Iterator;
现在使用foreach处理该类的用例能够得到的行为和使用普通的for循环数组一样,但是他无需知道数据的表示方法是数组(即实现细节).对于本书中学习的和Java库中所包含的所有类似于集合的基础数据类型的实现,这一点非常总要.例如我们无需改变任何代码就可以随意切换不同的表示方法.更重要的是,从用例的角度来说,无需知晓类的实现细节用例也能实现迭代
一下算法十分重要,因为他几乎(但是还没有达到)达到了任意集合类数据类型的实现的最佳性能:
- 每项操作的用时都与集合大小无关
-空间需求总是不超过集合大小乘以一个常数
package 基础.背包队列栈;
import org.springframework.core.io.ClassPathResource;
import java.util.Iterator;
import java.util.Objects;
/**
* 下压栈(LIFO)(能够动态调整数组的大小的实现)
*/
public class ResizingArrayStack<Item> implements Iterable<Item>{
private Item[] a = (Item[]) new Object[1];//栈元素
private int N = 0;//元素数量
public boolean isEmpty(){
return N==0;
}
/**
* 修改栈数组大小
* @param max
*/
public void resize(int max){
//将栈移动到一个大小为max的新数组
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i ++){
temp[i]=a[i];
}
a=temp;
}
public int size(){
return N;
}
/**
* 添加新元素
* @param item
*/
public void push(Item item){
//将元素添加到栈顶
if (N == a.length) resize(2*a.length);
a[N++]=item;
}
/**
* 删除元素
* @return
*/
public Item pop(){
Item item = a[--N];
a[N]=null;//避免对象游离
if (N > 0 && N == a.length/4){
resize(a.length/2);
}
return item;
}
@Override
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item>{
//支持后进先出的迭代
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
}
}
这份泛型的可迭代的Stack Api的实现是所有集合类抽象数据类型实现的一个模板.他将所有元素保存在数组中,并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数
链表
链表是在集合类的抽象数据类型实现中表示数据的合适选择.这是我们构造非Java支持的数据结构的第一个例子.我们的实现将成为这本书中其他更加复杂的数据结构的构造代码的模板.
- 链表定义:链表是一种递归的数据结构,他或者空(null),或者指向一个结点(Node)的引用,在该节点含有一个泛型的元素和一个指向另一条链表的引用
结点记录
在面向对象编程中,实现链表并不困难.我们首先用一个嵌套类来定义结点的抽象数据了类型
private class Node{
Item item;
Node node;
}
我们会在需要使用Node类的类中定义他并将它标记为private,因为他不是为用例准备的.和任意数据结构一样,我们通过new Node()触发(无参数的)构造函数来创建一个Node类型的对象.
调用结果指向一个Node对象的引用,他的实例变量均被初始化为null.
Item是一个占位符,表示我们希望用链表处理的任意数据类型(我们将会使用Java泛型使之表示任意引用类型)
构造链表
现在根据递归的定义,我们只需要一个Node类型的变量就可以表示一条链表,只要保证他的值是null或者指向另一个Node对象且该对象的next域指向了另外一条链表即可.要构造一条含有元素to,be和or的链表
- 首先为每一个元素创造一个结点
Node first = new Node();
Node second = new Node();
Node thirst = new Node();
- 并将每个结点的item域设置为所需要的值(Item为String)
first.item = "to";
second.item = "be";
third.item = "or"'
- 然后设置next域来构造链表
first.next=second;
second.next=third;
注意,third.next仍然是null,即创建的初始值
在构建链表或者其他链式结构的代码时,我们会使用可视化表示方法:
- 用长方形表示对象
- 将实例变量的值写在长方形中
- 用指向被引用对象的箭头表示引用关系
在表头插入元素
如果要在首结点为first的给定链表开头插入字符串not,我们现将first保存在oldFirst中,然后将一个新的结点赋予first,并将他的item设为not,next域设为oldFirst.所需时间与链表长度无关
从表头删除元素
只需要将first指向first.next即可
在表尾插入结点
我们需要一个指向链表最后一个结点的链接,因为该节点的链接必须被修改并指向含有一个新元素的新节点.当链表只有一个结点的时候,他既是首结点还是尾节点
其他位置的插入和删除操作
- 在表头插入结点
- 在表尾删除结点
- 在表尾插入节点
其他操作 - 删除指定的结点
- 在指定结点前插入一个新的结点
- 如何删除链表的尾结点?使用双向链表,其中每个链表都有两个链接,分别指向不同的方向
遍历
访问链表中的元素也有一个对应的方式:将循环的索引变量x初始化为链表的首结点,然后通过x.item访问和x相关联的元素,并将x设置为x.next来访问链表的下一个结点,如此反复,知道x为null为止(这说明我们已经到达了链表的尾部).这个过程被成为链表的遍历,可以用一下循环处理链表的每个结点的代码简介表达,其中first指向链表的首结点
for(Node x = first: x != null; x = x.next()){
//处理x.item
}
栈的实现
- 将栈保存为一条链表,栈的顶部即为表头,实例变量first指向栈顶
- push()压入一个元素时,我们会将该元素添加到表头
- pop()删除一个元素时,我们会将元素从表头删除
- 实现size()方法,用实例变量N保存元素的个数,在压入元素时将N+1,在弹出元素时将N-1
- 要实现isEmpty()方法,只要检查first是否为null或者检查N是否为0
- 该实现使用了泛型Item
- 暂时忽略迭代代码
链表的使用达到了我们最优设计目标:
- 他可以处理任意类型的数据
- 所需的空间总是和集合的大小成正比
- 操作所需的时间总是和集合的大小无关
下压堆栈表API实现(链表实现)
package 基础.背包队列栈;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 下压栈
* @param <Item>
*/
public class Stack<Item> implements Iterable<Item> {
//下压栈栈顶(最近添加的元素)
private Node first;
//元素数量
private int N;
/**
* 空构造函数
*/
public Stack() {
}
/**
* 添加一个元素
* @param item
*/
public void push(Item item){
//
Node oldFirst = first;
first = new Node();
first.item=item;
first.next=oldFirst;
N++;
}
/**
* 删除最近添加的元素
* @return
*/
public Item pop(){
// if (first == null){
// throw new NoSuchElementException();
// }
Item item = first.item;
first=first.next;
N--;
return item;
}
/**
* 栈是否为空
* @return
*/
public boolean isEmpty(){
return first==null;
}//或者:N==0
/**
* 栈中元素数量
* @return
*/
public int size(){
return N;
}
@Override
public Iterator<Item> iterator() {
return new StackIterator(first);
}
private class StackIterator implements Iterator<Item>{
private Node current;
public StackIterator(Node first) {
this.current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if (!hasNext()){
throw new NoSuchElementException();
}
Item item = current.item;
current = current.next;
return item;
}
}
private class Node{
//定义了结点的嵌套类
Item item;
Node next;
}
}
队列的实现
- 队列表示为一条从最早插入元素到最近插入元素的链表,实例变量first指向队列开头,实例变量last指向队列的结尾
- 元素入列(qnqueue())我们将他添加到表尾(链表为空的时候,first和last都指向新节点)
- 元素出列(dequeue())我们就要删除表头的结点(和Stack一样,当链表为空的时候需要更新last的值)
- 实现size()方法,用实例变量N保存元素的个数,在压入元素时将N+1,在弹出元素时将N-1
- 要实现isEmpty()方法,只要检查first是否为null或者检查N是否为0
- 该实现使用了泛型Item
- 暂时忽略迭代代码
链表的使用达到了我们最优设计目标:
- 他可以处理任意类型的数据
- 所需的空间总是和集合的大小成正比
- 操作所需的时间总是和集合的大小无关
先进先出队列API实现
package 基础.背包队列栈;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 先进先出队列
* @param <Item>
*/
public class Queue<Item> implements Iterable<Item> {
//最早添加的结点的链接
private Node first;
//最近添加的结点的链接
private Node last;
//队列中元素的数量
private int N;
/**
* 添加一个元素
* @param item
*/
public void enqueue(Item item){
//向对尾添加元素
Node oldLast = last;
last.item=item;
last.next=null;
if (isEmpty()){
first = last;
}else{
oldLast.next=last;
}
N++;
}
public int size(){
return N;
}
/**
* 删除表头元素
*/
public Item dequeue(){
// if (isEmpty()){
//
// throw new NoSuchElementException();
// }
//从表头删除元素
Item item = first.item;
first=first.next;
if (isEmpty()){
last=null;
}
N--;
return item;
}
/**
* 空构造函数
*/
public Queue() {
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return first == null;
}//或者N==0
/**
* 迭代器
* @return
*/
@Override
public Iterator<Item> iterator() {
return new QueueStack(first);
}
private class QueueStack implements Iterator<Item>{
private Node current;
public QueueStack(Node first) {
this.current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if (!hasNext()){
throw new NoSuchElementException();
}
Item item = current.item;
current=current.next;
return item;
}
}
private class Node{
//定义了结点的嵌套类
Item item;
Node next;
}
}
在结构化存储数据集时,链表是数组的一种重要替代方案
背包的实现-集合类型中实现迭代
- 将栈保存为一条链表,栈的顶部即为表头,实例变量first指向栈顶
- add()压入一个元素时,我们会将该元素添加到表头
- 实现size()方法,用实例变量N保存元素的个数,在压入元素时将N+1,在弹出元素时将N-1
- 要实现isEmpty()方法,只要检查first是否为null或者检查N是否为0
- 该实现使用了泛型Item
- 暂时忽略迭代代码
链表的使用达到了我们最优设计目标:
- 他可以处理任意类型的数据
- 所需的空间总是和集合的大小成正比
- 操作所需的时间总是和集合的大小无关
集合类型中实现迭代
- 第一步添加下面的代码
import java.util.Iterator
- 第二步,在类的声明中添加一下代码,他保证类必然会提供一个iterator()方法
implements Iterable<Item>
iterator()方法本身只是简单的从实现了Iterator接口的类中返回一个对象:
public Iterator<Item> iterator(){
return new ListIterator();
}
这段代码保证了类必然会实现方法hasNext(),next()和remove(),供用例的foreach语句使用.
要实现这些方法,嵌套类ListIterator()维护了一个实例变量current来记录链表的当前结点.hasNext()方法会检测current是否为null,next()方法会保存当前元素的引用,将current变量指向链表的下一个结点并返回所保存的引用
package 基础.背包队列栈;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 定义泛型背包类
*/
public class Bag<Item> implements Iterable<Item> {
//泛型元素链表
private Node first;
//元素数量
private int N;
//当前链表指向的元素
/**
* 创建一个控背包
*/
public Bag() {
}
/**
* 添加一个元素
* @param item
*/
public void add(Item item){
Node oldFirst = first;
first = new Node();
first.item=item;
first.next=oldFirst;
N++;
}
/**
* 背包是否为空
* @return
*/
public boolean isEmpty(){
return first==null;
}
// public Iterator iterator(){
// return (Iterator) new ListIterator<Item>(first);
// }
/**
* 背包中元素的数量
* @return
*/
public int size(){
return N;
}
/**
* 实现一个迭代器
* @return
*/
@Override
public Iterator<Item> iterator() {
return new ListIterator(first);
}
/**
* 具体迭代器实现
*
*/
private class ListIterator implements Iterator<Item> {
private Node current = first;
/**
* 使用背包的链表子元素
* @param first
*/
public ListIterator(Node first) {
this.current = first;
}
/**
* 链表是否为空
* @return
*/
public boolean hasNext() {
return current != null;
}
public void remove(){
throw new UnsupportedOperationException();
}
/**
* 当前链表的下一个元素
* @return
*/
public Item next() {
// if (!hasNext()){
// throw new NoSuchElementException();
// }
Item item = current.item;
current=current.next;
return item;
}
}
private class Node{
//定义了结点的嵌套类
Item item;
Node next;
}
}