(数据结构与算法分析笔记)第三章 表 栈 队列

java

程序中最基本的三种数据结构：表 栈 队列

抽象数据类型ADT

抽象数据类型 是带有一组操作的一些对象的集合，抽象数据类型是数学的抽象。

表ADT

表的ADT包括printList,makeEmpty,find,insert,remove,findKthnext,previous等，当然，一个方法的功能如何恰当，完全由程序的设计者决定

表的简单数组实现

对表的所有ADT操作都可以通过使用数组来实现，虽然数组的容量是固定的，但在需要的时候可以通过创建一个更大的数组来替换原来的数组，如下例子：

1
2
3
4
5
6
7
int [] aar = new int [10];
//下面我们来扩大aar
int [] newaar = new int [aar.length*2];
for(int i = 0;i < aar.length;i++){
    newaar[i] = aar[i];
}
aar = newaar;

数组的实现可以使得printList以线性的时间被执行，findKth操作则花费常数的时间，但插入以及删除却潜藏昂贵的开销。最坏情况是在位置为0插入或者删除数据，需要的时间为：$O(N)$

简单链表

为避免插入和删除的线性开销，我们需要保证表可以不连续存储，否则表的每一个部分都可能需要整体移动，链表是由一系列节点组成，这些节点不必在内存中相连，每一个节点均含有表元素和到包含该元素后继元的节点的链（link）,我们称之next链，最后一个单元的next链引用null.
让每一个节点都有一个指向它在表中的前驱节点的链，叫做双链表

Java Collections API中的表
Collection 接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface  Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    void clear();
}

Collection接口扩展了Iterable接口（extends Iterable），实现Iterable接口的类可以拥有增强for循环，该循环施于这些类上观察他们所有的项。

1
2
3
4
5
// 接口既可以继承其他接口但不能实现其他接口。也就是说你可以这些写：
public interface secondInterface extends FirstInterface
//但是你绝对不能这么写：
public interface Collection implements Iterable<T>
//接口无法实现另外一个借口，只有类才会实现接口。

print的增强for循环例子

1
2
3
4
5
public static <T> void print(Collection<T> coll){
    for(T t : coll){
        System.out.println(t);
    }
}

Iterator接口

实现Iterable接口的集合必须提供一个称为iterator的方法，该方法返回一个Iterator类型的对象。

1
2
3
4
5
6
7
8
9
10
11
public interface   Iterable<T> {
     Iterator<T> iterator;
     /**接口中只能定义方法名，而不能包含方法的具体实现代码。接口中定义的方法必须在接口的非抽象子类中实现。,因为接口有这个语法限制，所以要直接改变/扩展接口内的方法变得非常困难。我们在尝试强化Java 8 Collections API，让其支持lambda表达式的时候，就面临了这样的挑战。为了克服这个困难，Java 8中引入了一个新的概念，叫做default方法，也可以称为Defender方法，或者虚拟扩展方法（Virtual extension methods)。
     Default方法是指，在接口内部包含了一些默认的方法实现（也就是接口中可以包含方法体，这打破了Java之前版本对接口的语法限制），从而使得接口在进行扩展的时候，不会破坏与接口相关的实现类代码。**/
     default void forEach(Consume<? super T> action){
         Objects.requireNonNull(action);
         for(T t : this){
             action.accept(t);
         }
     }
}

1
2
3
4
5
6
7
public interface Iterator<E>{
      boolean hasNext();
      E next();
      default void remove(){
         throw new UnsupportedOperationException("remove");
      }
}

Iterator接口的思路是通过iterator方法，每一个集合都可以创建并返回给客户一个实现Iterator接口的对象，并将当前位置的概念在对象内部存储下来。每一次对next的调用都给出集合的下一项，因此第一次调用next给出第一项，第二次调用给出第二项，等等。hasNext用来告诉是否存在下一项。当编译器见到一个正在用于Iterable的对象的增强的for循环的时候，他用对iterator方法的那些调用代替增强的for循环以得到一个Iterator对象，然后调用next和hasNext.所以以上的print例子会由编译器重写：

1
2
3
4
5
6
7
public static T void print(Collection<T> coll){
    Iterator<T> itr = coll.iterator();
    while(itr.hasNext()){
        T  t = itr.next();
        System.out.println(t);
    }
}

Iterator接口的现有方法有限，难以实现遍历Collection以外的任何工作，Iterator接口还有一个remove方法，该方法可以删除next最新返回的项，此后我们不能在调用remove一直到下一次调用next以后，Iterator的remove方法可以知道所删除的项目的准确位置，但Collection里面的remove方法需要首相查找被删除的项，，同时如果对正在被迭代的集合进行结构上的改变（即对该集合使用add,remove,clear方法），那么迭代器就不合法，并且在其后使用该迭代器会抛出ConcurrentModificationException异常，而用了迭代器自己的remove方法，那么这个迭代器还是合法的。

List接口，ArrayList类，LinkedList类

List接口继承了Collection接口，因此他包含Collection接口的所有方法。

1
2
3
4
5
6
7
8
9
10
public interface   List<E> extends Collection<E> {
     E get(int index);
     E set(int index, E element);
     int indexOf(Object o);
     int lastIndexOf(Object o);
     ListIterator<E>  listIterator();
     ListIterator<E>   listIterator(int index);
     List<E>   subList(int fromIndex, int toIndex);
     ....
}

List接口指定listIterator 方法，他将产生比通常认为的更复杂的迭代器，JDK里面的源码为：

1
2
3
4
5
6
7
8
9
10
11
public interface  ListIterator<E> extends Iterator<E> {
    boolean  hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

List ADT有两种流行的实现方式。ArrayList类提供了可增长数组的实现，该类对于get和set的调用花费常数的时间，但在删除以及插入需要时间最坏为：$O(N^2)$。LinkedList类提供了双链表实现，该类新项的插入或者现有项的删除代价较低，但不容易做索引，因此对get的操作是昂贵的。

ArrayList
LinkedList

栈ADT

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶，对栈的基本操作有进栈(push)和出栈(poll)。栈有叫做LIFO（后进先出）表。
JDK提供了Stack类实现栈的ADT

1
2
3
public class Stack<E>  extends Vector<E>{
    ...
}

队列ADT

队列也是表，但是使用队列插入在一端进行，删除在另外一端进行。队列的基本操作是enqueue（入队）和dequeue（出对）,enqueue(入队)它是在表的末端（队尾）插入一个元素，dequeue（出对）是删除（并返回）在表的开头的元素。和栈一样，队列的任何的表的实现都是可以的，操作也是开速的。队列的链表实现是最简单直接的。JDK提供的队列的ADT如下：

1
2
3
public interface Queue<E> extends Collection<E>{
   ...
}

队列的类为：
抽象类：java.util.concurrent.BlockingQueue
实现类：
java.util.concurrent.LinkedBlockingQueue：大小不定的BlockingQueue,若其构造函数带一个规定大小的参数,生成的BlockingQueue有大小限制,若不带大小参数,所生成的BlockingQueue的大小由Integer.MAX_VALUE来决定.其所含的对象是以FIFO(先入先出)顺序排序的。
java.util.concurrent.ArrayBlockingQueue：一个由数组支持的有界阻塞队列，规定大小的BlockingQueue,其构造函数必须带一个int参数来指明其大小.其所含的对象是以FIFO(先入先出)顺序排序的。
java.util.concurrent.PriorityBlockingQueue：类似于LinkedBlockQueue,但其所含对象的排序不是FIFO,而是依据对象的自然排序顺序或者是构造函数的Comparator决定的顺序。
java.util.concurrent.SynchronousQueue：特殊的BlockingQueue,对其的操作必须是放和取交替完成的。

本文标题:(数据结构与算法分析笔记)第三章 表 栈 队列

文章作者:剑客爱编程

发布时间:2016-07-08, 23:50:21

最后更新:2016-07-08, 23:50:21

原始链接:https://iskylove.github.io/2016/07/08/java_datastructures_alogorithm_2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 抽象数据类型ADT
  2. 2. 表ADT
    1. 2.1. 表的简单数组实现
    2. 2.2. 简单链表
  3. 3. Java Collections API中的表
    1. 3.1. Collection 接口
    2. 3.2. Iterator接口
    3. 3.3. List接口，ArrayList类，LinkedList类
  4. 4. 栈ADT
  5. 5. 队列ADT
,