所謂序列（Sequence），就是依次排列的多個對象钾挟。比如何什，每一計算機程序都可以看作一個序列，它由一系列依次排列的指令組成等龙，正是指令之間的次序決定了程序的具體功能处渣。因此，所謂序列蛛砰，就是一組對象之間的后繼與前驅關系罐栈。在實際問題中，序列可以用來實現(xiàn)很多種數(shù)據(jù)結構泥畅，因此被認為是數(shù)據(jù)結構設計的基礎荠诬。
棧、隊列以及雙端隊列位仁，都可以看作帶有附加限制的序列柑贞。
** 向量（Vector）和列表（List）都屬于序列 **
一，向量
對數(shù)組結構進行抽象與擴展之后聂抢，就可以得到向量結構钧嘶，因此向量也稱作數(shù)組列表（Array list）。向量提供一些訪問方法琳疏，使得我們可以通過下標直接訪問序列中的元素有决，也可以將指定下標處的元素刪除闸拿，或將新元素插入至指定下標。為了與通常數(shù)組結構的下標（Index）概念區(qū)分開來书幕，我們通常將序列的下標稱為秩（Rank）新荤。
假定集合 S 由n 個元素組成，它們按照線性次序存放台汇，于是我們就可以直接訪問其中的第一個元素苛骨、第二個元素、第三個元素……苟呐。也就是說智袭，通過[0, n-1]之間的每一個整數(shù)，都可以直接訪問到唯一的元素e掠抬，而這個整數(shù)就等于S 中位于e 之前的元素個數(shù)——在此吼野，我們稱之為該元素的秩（Rank）。不難看出两波，若元素e 的秩為r瞳步，則只要e 的直接前驅（或直接后繼）存在，其秩就是r-1（或r+1）腰奋。
支持通過秩直接訪問其中元素的序列单起，稱作向量（Vector）或數(shù)組列表（Array list）。實際上劣坊，秩這一直觀概念的功能非常強大——它可以直接指定插入或刪除元素的位置嘀倒。
二，向量ADT(AbstractDataType)
| 操作方法 | 功能描述 |
|---|---|
| getSize() | 報告向量中的元素數(shù)目 輸入：無 輸出：非負整數(shù) |
| isEmpty() | 判斷向量是否為空 輸入：無 輸出：布爾值 |
| getAtRank(r) | 若0 ≤ r < getSize()局冰，則返回秩為r 的那個元素 测蘑；否則，報錯 輸入：一個整數(shù) 輸出：對象 |
| replaceAtRank(r, e) | 若0 ≤ r < getSize()康二，則將秩為r 的元素替換為e碳胳，并返回原來的元素 ；否則沫勿，報錯 輸入：一個整數(shù)和一個對象 輸出：對象 |
| insertAtRank(r, e) | 若0 ≤ r ≤ getSize()挨约，則將e 插入向量中，作為秩為r 的元素（原秩不小于r 的元素順次后移）产雹，并返回原來的元素 诫惭；否則，報錯 輸入：一個整數(shù)和一個對象 輸出：對象 |
| removeAtRank(r) | 若0 ≤ r < getSize()蔓挖，則刪除秩為r 的那個元素并返回之（原秩大于r 的元素順次前移）夕土；否則，報錯 輸入：一個整數(shù) 輸出：對象 |
三时甚，基于數(shù)組的簡單實現(xiàn)
向量接口：
package dsa.Vector;
/*
* 向量接口
*/
public interface Vector {
// 返回向量中元素數(shù)目
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;
}
當作為參數(shù)的秩越界時荒适，對應的意外錯為ExceptionBoundaryViolation:
package dsa.Vector;
/*
* 當作為參數(shù)的數(shù)組下標梨熙、向量的秩或列表的位置越界時，本意外將被拋出
*/
public class ExceptionBoundaryViolation extends RuntimeException {
public ExceptionBoundaryViolation(String err) {
super(err);
}
}
基于數(shù)組刀诬，可以直接實現(xiàn)向量ADT:
package dsa.Vector;
/*
* 基于數(shù)組的向量實現(xiàn)
*/
public class Vector_Array implements Vector {
private final int N = 1024;// 數(shù)組的容量
private int n = 0;// 向量的實際規(guī)模
private Object[] A;// 對象數(shù)組
// 構造函數(shù)
public Vector_Array() {
A = new Object[N];
n = 0;
}
// 返回向量中元素數(shù)目
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("意外：數(shù)組溢出");
for (int i = n; i > r; i--)
A[i] = A[i - 1];// 后續(xù)元素順次后移
A[r] = obj;// 插入
n++;// 更新當前規(guī)模
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];// 后續(xù)元素順次前移
n--;// 更新當前規(guī)模
return bak;
}
}
四陕壹，基于可擴充數(shù)組的向量實現(xiàn)
上面給出的向量實現(xiàn)质欲，有個很大的缺陷——數(shù)組容量N固定，我們希望向量能夠根據(jù)實際需要糠馆，動態(tài)地擴充數(shù)組的容量嘶伟。當然，Java 語言本身并不支持這一功能又碌，與多數(shù)程序語言一樣九昧，Java 中數(shù)組的容量都是固定的。我們的策略是毕匀，一旦數(shù)組空間溢出（即n≥N）铸鹰，insertAtRank()方法就會做如下處理：
- 開辟一個容量為2N的新數(shù)組B
- 將A[ ]中各元素搬遷至B[ ]，即B[i]=A[i]皂岔，i=0, …, N-1
- 將A替換為B蹋笼，即令A=B
package dsa.Vector;
/*
* 基于可擴充數(shù)組的向量實現(xiàn)
*/
public class Vector_ExtArray implements Vector {
private int N = 8;// 數(shù)組的容量，可不斷增加
private int n;// 向量的實際規(guī)模
private Object A[];// 對象數(shù)組
// 構造函數(shù)
public Vector_ExtArray() {
A = new Object[N];
n = 0;
}
// 返回向量中元素數(shù)目
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];// 開辟一個容量加倍的數(shù)組
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];// 后續(xù)元素順次后移
A[r] = obj;// 插入
n++;// 更新當前規(guī)模
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];// 后續(xù)元素順次前移
n--;// 更新當前規(guī)模
return bak;
}
}
Java本身也提供了與向量ADT功能類似的兩個類：java.util.ArrayList和java.util.Vector。
