2.3 线性结构
前面在介绍线性结构的时候已经提到，常用的线性结构有线性表、栈和队列等。本节将简要介绍线性表、栈和队列的概念，并且采用面向接口编程的方式，使用Java语言确定这些逻辑结构的基本操作接口。
2.3.1 线性表的存储结构
线性表的结构特点主要表现在两个方面：一是均匀性，虽然不同数据表的数据元素可以是各式各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。二是有序性，各数据元素在线性表中按序排列，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其他元素前面均只有一个数据元素（直接前驱）且后面均只有一个数据元素（直接后继）。
在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。栈、队列是线性表的特殊情况，是受限的线性结构，只是在数据结构的操作上有区别，在存储结构方面和线性表一样。
线性表的顺序存储结构如图2.8所示。
线性表的链式存储有三种形式：单链表、循环链表和双向链表。
- 单链表
在单链表中，每个节点都包含指向下一个节点的指针，最后一个节点的指针为空，以标记是最后一个节点。之所以称为单链表是因为每个节点只存在一个节点指针，所以只能依次顺序访问下一个节点，访问完某节点之后再想往回查找是不可以的。为了记住单链表的第一个位置，可以定义一个头指针。单链表的链式存储结构如图2.7所示。
- 循环链表
在单链表的基础上，可以让最后一个节点的指针指向第一个节点，这样循环起来形成的链表即为循环链表。循环列表可以顺序访问下一个节点，访问完某节点之后可以通过下一个循环再次访问到该节点。为了记住单链表的第一个位置和最后一个位置，可以定义一个头指针和一个尾指针。循环链表的链式存储结构如图2.9所示。
- 双向链表
双向链表比单链表多出了一个节点指针，用来指向前一个节点的数据，这样做的好处是避免了寻找前面节点时发生的不便之举。双向链表的链式存储结构如图2.10所示。
2.3.2 线性表
通过对线性结构的分析，可得到如下结论：对线性结构的主要操作有查找线性结构中某个信息、修改线性结构中某个信息、在固定的位置插入和删除相应的信息等，即查询、插入、删除、修改等相关操作。接下来以面向接口编程的方式，定义一个线性表接口，该接口具有如下基本操作。
（1）插入数据元素。
（2）删除数据元素。
（3）替换数据元素。
（4）获取数据元素。
（5）获取线性表中数据元素个数。
（6）判断线性表是否为空。
下面是线性表接口的代码：
public interface List {
//在指定下标位置插入数据元素
public void insert(int i, Object obj) throws Exception;
//删除指定下标位置的数据元素
public Object delete(int i) throws Exception;
//替换指定下标位置的数据元素
public void update(int i, Object obj) throws Exception;
//获取指定下标位置的数据元素
public Object getData(int i) throws Exception;
//获取线性表数据元素个数
public int size();
//判断线性表是否为空
public boolean isEmpty();
}
copy接下来用顺序存储结构的数组，来存储线性表的逻辑结构，同时实现上面定义的List接口。请认真阅读该段代码，细节部分已通过注释加以描述，具体代码如下：
public class SeqList implements List{
final int defaultSize = 10; //默认线性表长度
int maxSize; //线性表长度
int size; //线性表中现有元素个数
Object[] listArray; //用对象数组存储线性表
//无参构造方法
SeqList(){
initiate(defaultSize);
}
//带线性表长度的构造方法
SeqList(int size){
initiate(size);
}
//初始化方法，设置线性表长度、现有元素个数和初始化对象数组（用线性表长度）
public void initiate(int sz){
maxSize = sz;
size = 0;
listArray = new Object[sz];
}
//实现在指定下标位置插入数据元素
public void insert(int i,Object obj) throws Exception{
if (size == maxSize){
throw new Exception("线性表已满，无法插入！");
}
//只允许在现有线性表数据元素之前或之后插入，不允许隔着一个空位置之后插入数据元素
if (i > size){
throw new Exception("插入下标位置错误！");
}
//将插入位置后的数据元素全部后移
for(int j = size; j > i; j--){
listArray[j] = listArray[j-1];
}
//插入数据元素，并增加线性表中现有元素个数
listArray[i] = obj;
size++;
}
//实现删除指定下标位置的数据元素
public Object delete(int i) throws Exception{
if(size == 0){
throw new Exception("线性表已空，无法删除！");
}
if (i > size-1){
throw new Exception("删除下标位置错误！");
}
//获得被删除的数据元素
Object it = listArray[i];
//将删除位置后的数据元素全部前移
for(int j = i; j < size-1; j++){
listArray[j] = listArray[j+1];
}
//返回被删除数据元素，并减少线性表中现有元素个数
size--;
return it;
}
//实现替换指定下标位置的数据元素
public void update(int i, Object obj) throws Exception{
if(size == 0){
throw new Exception("线性表已空，无法替换！");
}
if (i > size-1){
throw new Exception("替换下标位置错误！");
}
//替换指定下标的数据元素
listArray[i] = obj;
}
//实现获取指定下标位置的数据元素
public Object getData(int i) throws Exception{
if(size == 0){
throw new Exception("线性表已空，无法获取！");
}
if(i >= size){
throw new Exception("获得下标位置错误！");
}
return listArray[i];
}
//实现获取线性表数据元素个数
public int size(){
return size;
}
//实现判断线性表是否为空
public boolean isEmpty(){
return size == 0;
}
}
copy上述代码中，关于插入位置i和线性表中现有元素个数size的比较非常细致，也正确体现了线性表的特性，需要认真理解。例如在实现在指定下标位置插入数据元素的代码中，if(i > size){…}这行判断语句，可以理解为如果线性表中现有3个数据元素，即size值为3，则只允许在下标为0、1、2、3这四个位置（其中下标为3的这个位置是第一个空着的位置）插入数据元素，不允许让下标为3的位置空着，在下标大于3的位置插入数据元素。
2.3.3 栈
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读取数据的时候是从栈顶开始弹出数据（最后一个进入的数据被第一个读出来）。
仍然以面向接口编程的方式，定义一个栈接口，该接口具有如下基本操作。
（1）把数据元素压入栈—进栈。
（2）获取并删除栈顶数据元素—退栈。
（3）获取但不删除栈顶数据元素。
（4）判断栈是否为空。
下面是栈接口的代码：
public interface Stack{
//把数据元素压入栈—进栈
public void push(Object obj) throws Exception;
//获取并删除栈顶数据元素—退栈
public Object pop() throws Exception;
//获取但不删除栈顶数据元素
public Object getTop() throws Exception;
//判断栈是否为空
public boolean notEmpty();
}
copy接下来仍然用顺序存储结构的数组来存储栈的逻辑结构，同时实现上面定义的Stack接口，具体代码如下：
public class SeqStack implements Stack{
final int defaultSize = 10;
int top;//标记栈内元素个数，即栈顶元素
Object[] stack;
int maxStackSize;
public SeqStack(){
initiate(defaultSize);
}
public SeqStack(int sz){
initiate(sz);
}
private void initiate(int sz){
maxStackSize = sz;
top = 0;
stack = new Object[sz];
}
//实现把数据元素压入栈—进栈
public void push(Object obj) throws Exception{
if(top == maxStackSize){
throw new Exception("堆栈已满！");
}
//进栈，栈顶标记加1
stack[top] = obj;
top++;
}
//实现获取并删除栈顶数据元素—退栈
public Object pop() throws Exception{
if(top == 0){
throw new Exception("堆栈已空！");
}
//返回退栈数据元素，栈顶标记减1实现删除（实际并未删除）
top--;
return stack[top];
}
//实现获取但不删除栈顶数据元素
public Object getTop() throws Exception{
if(top == 0){
throw new Exception("堆栈已空！");
}
return stack[top - 1];
}
//实现判断栈是否为空
public boolean notEmpty(){
return (top > 0);
}
}
copy该段代码比较简单，唯一需要注意的是在实现获取并删除栈顶数据元素—退栈的操作时，并没有真正删除该数据元素，而是通过top栈顶标记减1实现删除的。
接下来的程序演示了如何使用栈这样的数据结构，具体代码如下：
public class TestSeqStack{
public static void main(String[] args){
//创建一个空栈
SeqStack myStack = new SeqStack();
int test[] = {1, 3, 5, 7, 9};
int n = 5;
try{
//依次将长度为5的整型数组中的数转换为Integer类型入栈
for(int i = 0; i < n; i++){
myStack.push(new Integer(test[i]));
}
//获取栈顶元素
System.out.println("当前栈顶元素为：" + myStack.getTop());
System.out.println("元素出栈序列为：");
while(myStack.notEmpty()){ //判断栈是否为空
System.out.println(myStack.pop()); //逐个出栈
}
}catch(Exception e){
System.out.println(e.getMessage());
}
}
}
copy编译、运行程序，程序运行结果如图2.11所示。
2.3.4 队列
队列也是一种特殊的线性结构，它只允许在该结构的前端进行删除操作，在后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素，反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”的线性结构。
接下来定义一个队列接口，该接口具有如下基本操作。
（1）把数据元素插入队列尾部—入队。
（2）获取并删除队列头部数据元素—出队。
（3）获取但不删除队列头部数据元素。
（4）判断队列是否为空。
下面是队列接口的代码：
public interface Queue{
//把数据元素插入队列尾部—入队
public void EnQueue(Object obj) throws Exception;
//获取并删除队列头部数据元素—出队
public Object DeQueue() throws Exception;
//获取但不删除队列头部数据元素
public Object QueueFront() throws Exception;
//判断队列是否为空
public boolean notEmpty();
}
copy关于如何使用数组来存储队列的逻辑结构，同时实现上面定义的Queue接口，将是留给大家的上机任务。