数据结构――栈、队列和树(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 inte易做图ce 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()

    {

    if (top < 0)

        throw new java.util.EmptyStackException();

    

    return stack[top--];

    }

}

ArrayStack表明，栈由私有整型索引top和一维数组的引用变量stack组成。top标识stack中的栈顶数据项，初始化为－1以表示栈为空。当要创建一个ArrayStack对象时使用一个说明元素最大数目的整型值来调用public ArrayStack(int maxElements)。试图从一个空栈的栈顶弹出一个数据项会使得pop()函数里抛出一个java.util.EmptyStackException异常对象。与之相似，如果试图在栈中压入多于maxElements的数据项会使得push(Object o)函数抛出FullStackException对象，其代码见清单10:

清单10 FullStackException.java

package com.javajeff.cds;

public class FullStackException extends RuntimeException

{

}

为了与EmptyStackException相对称，FullStackException扩展了RuntimeException。这样，你就不必在一个方法的throws从句里加上FullStackException。

    清单11 给出了Stack的基于单链表的实现：

清单11. LinkedListStack.java

// LinkedListStack.java

 

package com.javajeff.cds;

 

public class LinkedListStack implements Stack

{

    private static class Node

    {

    Object o;

    Node next;

    }

 

    private Node top = null;

 

    public boolean imEmpty()

    {

    return top == null;

    }

 

    public Object peek()

    {

        if (top == null)

        throw new java.util.EmptyStackException();

    return top.o;

    }

 

    public void push(Object o)

    {

    Node temp = new Node();

    temp.o = o;

    temp.next = top;

    top = temp;

    }

 

    public Object pop()

    {

    if (top == null)

        throw new java.util.EmptyStackException();

 

    Object o = top.o;

    top = top.next;

    return o;

    }

}

LinkedListStack表明栈由一个私有的顶层嵌套类Node和一个私有引用变量top构成，引用变量top初始化为null表示一个空栈。相对于一维数组实现的栈，LinkedListStack并不需要一个构造器，因为它能够随着数据项的压入动态扩展。这样，void push(Object o)就不需要抛出FullStackException对象。然而，Object pop()还是需要检查栈是否为空的，这可能会导致可抛的EmptyStackException对象。

因为我们已经看到了构成栈这一数据结构实现的接口和三个类，我们就来示例一下栈的使用。

清单 12. StackDemo.java 

// StackDemo.java

 

import com.javajeff.cds.*;

 

class StackDemo 

{

    public static void main(String[] args)

    {

    System.out.println("ArrayStack Demo");

    System.out.println("---------------");

 

    stackDemo(new ArrayStack(5));

 

    System.out.println("LinkedListStack Demo");

    System.out.println("---------------------");

 

    stackDemo(new LinkedListStack());

    }

 

    statci void stackDemo(Stack s)

    {

    System.out.println("Pushing \"Hello\"");

    s.push("Hello");

 

    System.out.println("Pushing \" World\"");

    s.push("World");

 

        System.out.println("Pushing StackDemo Object");

    s.push(new StackDemo());

 

    System.out.println("Pushing Character object");

    s.push(new Character("A"));

 

    try 

    {

        System.out.println("Pushing \"One last item\"");

        s.push("One last item");

    } catch(FullStackException e)

        {

        System.out.println ("One push too many");

    }

 

    System.out.println();

 

    while (!s.imEmpty())

        System.out.println(s.pop());

 

    try

        {

        s.pop();

    }

    catch(java.util.EmptyStackException e)

    {

        System.out.println();   

    }

 

    System.out.println();

    }

}

当运行StackDemo时产生如下输出：

ArrayStack Demo
---------------
Pushing "Hello"
Pushing "World"
Pushing StackDemo object
Pushing Character object
Pushing Thread object
Pushing "One last item"
One push too many

Thread[A,5,main]
C
StackDemo@7182c1
World
Hello
One pop too many

LinkedListStack Demo
--------------------
Pushing "Hello"
Pushing "World"
Pushing StackDemo object
Pushing Character object
Pushing Thread object
Pushing "One last item"

上一个：产生彩色验证码_(javabean实现)
下一个：避免在Java中使用Checked Exception