数据结构――栈、队列和树(Java)

　　数据结构――栈、队列和树

开发者可以使用数组与链表的变体来建立更为复杂的数据结构。本节探究三种这样的数据结构:栈、队列与树。当给出算法时，出于简练，直接用Java代码。

栈

栈是这样一个数据结构，其数据项的插入和删除（获取）都只能在称为栈顶的一端完成。因为最后插入的数据项就是最先要删除的数据项，开发者往往将栈称为LILO（last-in, first-out）数据结构。

数据项压入（插入）或者弹出（删除或取得）栈顶。图13示例了一个有三个String数据项的栈，每个数据项压入栈顶。

图13 有三个以压入String数据项的栈

如图13所示，栈在内存中是向下建起来的。对于每个数据项的压入，之前栈顶的数据项以及其下面的所有数据项都得向下移，当要从栈中弹出一个数据项时，取得栈顶元素并将其从栈中删除。

栈在许多程序设计环境下非常有用。两个非常普通的环境：

·栈保存返回地址：当代码调用一个方法时，调用指令后的第一条指令的地址压入当前线程的方法调用栈的顶端。当执行被调用方法的返回指令时，该地址从栈顶弹出，然后从该地址处继续执行。假如一个方法调用了另一个方法，栈的LIFO行为模式确保了第二个方法的返回指令将执行转移到第一个方法，而第一个方法的返回指令能够将执行转移到调用第一个方法的代码的代码。结果就是，栈代表被调用方法“记住了”返回地址。

·栈保存每个被调用方法的参数和局部变量：当调用一个方法时，JVM在靠近返回地址处分配内存存储所有被调用方法的参数和局部变量。假如方法是个实例方法，存储在栈中的其中一个参数是当前对象的引用this。

一般可以使用一维数组或单链表实现一个栈。假如使用一维数组，一个常命名为top的整型变量保存栈顶数据项的索引。类似地，一个常命名为top的引用变量引用单链表情形下的栈顶节点（含有栈顶数据项）。

根据Java's Collections API中发现的体系结构建模栈的实现。这个实现由一个Stack接口，ArrayStack和LinkedListStack实现类以及FullStackException支持类组成。为了便于发布，将这些类打包在com.javajeff.cds包中，其中的cds表示复杂数据结构。清单8给出了Stack接口。

清单8. Stack.java

// Stack.java

package com.javajeff.cds;

public interface Stack
{
boolean isEmpty ();
Object peek ();
void push (Object o);
Object pop ();
}

Stack的四个方法分别是确定栈是否为空，获得栈顶数据项而没有删除，任意数据项入栈，获得并删除栈顶元素。除了一个具体于实现的构造方法之外，你的程序只需调用这些方法就足够了。

清单9 给出了Stack的基于一维数组的实现：

清单9 ArrayStack.java

// ArrayStack.java

package com.javajeff.cds;

public class ArrayStack implements Stack

{

private int top = -1;

private Object[] stack;

public ArrayStack(int maxElements)

{

stack = new Object[maxElements];

}

public boolean imEmpty()

{

return top == -1;

}

public Object peek()

{

if (top < 0)

throw new java.util.EmptyStackException();

return stack[top];

}

public void push(Object o)

{

if (top == stack.length - 1)

throw new FullStackException();

stack[++top] == 0;

}

public Object pop()