所谓序列（Sequence），就是依次排列的多个对象。比如，每一计算机程序都可以看作一个序列，它由一系列依次排列的指令组成，正是指令之间的次序决定了程序的具体功能。因此，所谓序列，就是一组对象之间的后继与前驱关系。在实际问题中，序列可以用来实现很多种数据结构，因此被认为是数据结构设计的基础。
栈、队列以及双端队列，都可以看作带有附加限制的序列。
** 向量（Vector）和列表（List）都属于序列 **
一，向量
对数组结构进行抽象与扩展之后，就可以得到向量结构，因此向量也称作数组列表（Array list）。向量提供一些访问方法，使得我们可以通过下标直接访问序列中的元素，也可以将指定下标处的元素删除，或将新元素插入至指定下标。为了与通常数组结构的下标（Index）概念区分开来，我们通常将序列的下标称为秩（Rank）。
假定集合 S 由n 个元素组成，它们按照线性次序存放，于是我们就可以直接访问其中的第一个元素、第二个元素、第三个元素……。也就是说，通过[0, n-1]之间的每一个整数，都可以直接访问到唯一的元素e，而这个整数就等于S 中位于e 之前的元素个数——在此，我们称之为该元素的秩（Rank）。不难看出，若元素e 的秩为r，则只要e 的直接前驱（或直接后继）存在，其秩就是r-1（或r+1）。
支持通过秩直接访问其中元素的序列，称作向量（Vector）或数组列表（Array list）。实际上，秩这一直观概念的功能非常强大——它可以直接指定插入或删除元素的位置。
二，向量ADT(AbstractDataType)
| 操作方法 | 功能描述 |
|---|---|
| getSize() | 报告向量中的元素数目 输入：无 输出：非负整数 |
| isEmpty() | 判断向量是否为空 输入：无 输出：布尔值 |
| getAtRank(r) | 若0 ≤ r < getSize()，则返回秩为r 的那个元素 ；否则，报错 输入：一个整数 输出：对象 |
| replaceAtRank(r, e) | 若0 ≤ r < getSize()，则将秩为r 的元素替换为e，并返回原来的元素 ；否则，报错 输入：一个整数和一个对象 输出：对象 |
| insertAtRank(r, e) | 若0 ≤ r ≤ getSize()，则将e 插入向量中，作为秩为r 的元素（原秩不小于r 的元素顺次后移），并返回原来的元素 ；否则，报错 输入：一个整数和一个对象 输出：对象 |
| removeAtRank(r) | 若0 ≤ r < getSize()，则删除秩为r 的那个元素并返回之（原秩大于r 的元素顺次前移）；否则，报错 输入：一个整数 输出：对象 |
三，基于数组的简单实现
向量接口：
package dsa.Vector;
/*
* 向量接口
*/
public interface Vector {
// 返回向量中元素数目
public int getSize();
// 判断向量是否为空
public boolean isEmpty();
// 取秩为r的元素
public Object getAtRank(int r) throws ExceptionBoundaryViolation;
// 将秩为r的元素替换为obj
public Object replaceAtRank(int r, Object obj)
throws ExceptionBoundaryViolation;
// 插入obj，作为秩为r的元素；返回该元素
public Object insertAtRank(int r, Object obj)
throws ExceptionBoundaryViolation;
// 删除秩为r的元素
public Object removeAtRank(int r) throws ExceptionBoundaryViolation;
}
当作为参数的秩越界时，对应的意外错为ExceptionBoundaryViolation:
package dsa.Vector;
/*
* 当作为参数的数组下标、向量的秩或列表的位置越界时，本意外将被抛出
*/
public class ExceptionBoundaryViolation extends RuntimeException {
public ExceptionBoundaryViolation(String err) {
super(err);
}
}
基于数组，可以直接实现向量ADT:
package dsa.Vector;
/*
* 基于数组的向量实现
*/
public class Vector_Array implements Vector {
private final int N = 1024;// 数组的容量
private int n = 0;// 向量的实际规模
private Object[] A;// 对象数组
// 构造函数
public Vector_Array() {
A = new Object[N];
n = 0;
}
// 返回向量中元素数目
public int getSize() {
return n;
}
// 判断向量是否为空
public boolean isEmpty() {
return (0 == n) ? true : false;
}
// 取秩为r的元素
public Object getAtRank(int r)// O(1)
throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
return A[r];
}
// 将秩为r的元素替换为obj
public Object replaceAtRank(int r, Object obj)
throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
Object bak = A[r];
A[r] = obj;
return bak;
}
// 插入obj，作为秩为r的元素；返回该元素
public Object insertAtRank(int r, Object obj)
throws ExceptionBoundaryViolation {
if (0 > r || r > n)
throw new ExceptionBoundaryViolation("意外：秩越界");
if (n >= N)
throw new ExceptionBoundaryViolation("意外：数组溢出");
for (int i = n; i > r; i--)
A[i] = A[i - 1];// 后续元素顺次后移
A[r] = obj;// 插入
n++;// 更新当前规模
return obj;
}
// 删除秩为r的元素
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
Object bak = A[r];
for (int i = r; i < n; i++)
A[i] = A[i + 1];// 后续元素顺次前移
n--;// 更新当前规模
return bak;
}
}
四，基于可扩充数组的向量实现
上面给出的向量实现，有个很大的缺陷——数组容量N固定，我们希望向量能够根据实际需要，动态地扩充数组的容量。当然，Java 语言本身并不支持这一功能，与多数程序语言一样，Java 中数组的容量都是固定的。我们的策略是，一旦数组空间溢出（即n≥N），insertAtRank()方法就会做如下处理：
- 开辟一个容量为2N的新数组B
- 将A[ ]中各元素搬迁至B[ ]，即B[i]=A[i]，i=0, …, N-1
- 将A替换为B，即令A=B
package dsa.Vector;
/*
* 基于可扩充数组的向量实现
*/
public class Vector_ExtArray implements Vector {
private int N = 8;// 数组的容量，可不断增加
private int n;// 向量的实际规模
private Object A[];// 对象数组
// 构造函数
public Vector_ExtArray() {
A = new Object[N];
n = 0;
}
// 返回向量中元素数目
public int getSize() {
return n;
}
// 判断向量是否为空
public boolean isEmpty() {
return (0 == n) ? true : false;
}
// 取秩为r的元素
public Object getAtRank(int r) throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
return A[r];
}
// 将秩为r的元素替换为obj
public Object replaceAtRank(int r, Object obj)
throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
Object bak = A[r];
A[r] = obj;
return bak;
}
// 插入obj，作为秩为r的元素；并返回该元素
public Object insertAtRank(int r, Object obj)
throws ExceptionBoundaryViolation {
if (0 > r || r > n)
throw new ExceptionBoundaryViolation("意外：秩越界");
if (N <= n) {// 空间溢出的处理
N *= 2;
Object B[] = new Object[N];// 开辟一个容量加倍的数组
for (int i = 0; i < n; i++)
B[i] = A[i];// A[]中内容复制至B[]
A = B;// 用B替换A（原A[]将被自动回收）
}
for (int i = n; i > r; i--)
A[i] = A[i - 1];// 后续元素顺次后移
A[r] = obj;// 插入
n++;// 更新当前规模
return obj;
}
// 删除秩为r的元素
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if (0 > r || r >= n)
throw new ExceptionBoundaryViolation("意外：秩越界");
Object bak = A[r];
for (int i = r; i < n - 1; i++)
A[i] = A[i + 1];// 后续元素顺次前移
n--;// 更新当前规模
return bak;
}
}
Java本身也提供了与向量ADT功能类似的两个类：java.util.ArrayList和java.util.Vector。
