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

{

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"

One last item
Thread[A,5,main]
C
StackDemo@cac268
World
Hello
One pop too many

队列

队列是这样一种数据结构，数据项的插入在一端（队列尾），而数据项的取得或删除则在另一端（队列头）。因为第一个插入的数据项也是第一个取得或删除的数据项，开发者普遍地将队列称为FIFO数据结构。

开发者经常使用到两种队列：线性队列和循环队列。在两种队列中，数据项都是在队列尾插入，然后移向队列头，并从队列头删除或获取。图14 说明了线性以及循环队列。


图14有四个已插入整型数据项的线性队列和七个数据项的循环队列

图14的线性队列存储四个数据项，整数1是第一个。队列已满，不能存储另外的整型数据项，因为rear已经指到了最右面（最后）的狭槽。front指向的狭槽为空，因为它涉及到线性队列的行为。起先，front和rear都指向最左边的狭槽，表示队列为空。为了存储整数1,rear指向右边的下一个狭槽，并将1存储到那个狭槽中。而当获取或删除整数1时，front向右前进一个狭槽。

图14的循环队列存储有七个整型数据项，以整数1开始。该队列为满并且不能存储别的整型数据，直至front沿顺时针方向前进一个狭槽。与线性队列相似，front指向的狭槽为空也是涉及到循环队列的行为。最初，front和rear指向同一个狭槽，表示队列为空。对于每个数据项插入，rear前进一个狭槽，对于每个数据项的删除，front前进一个狭槽。

队列在很多程序设计环境下非常有用。两个常见的情景有：

·线程调度：JVM或一个基本的操作系统会建立多个队列来反应不同的线程优先级。 线程信息会阻塞，因为给定优先级的所有线程存储在相关队列中。

·打印任务： 因为打印机的速度比计算机慢许多，操作系统将其打印任务分派给其打印子系统，打印子系统就会将这些任务插入到一个打印队列中。队列中的第一个任务先打印，最后一个任务最后打印。

开发者经常使用一维数组实现一个队列。然而，如果需要同时存在多个队列的话，或者因为优先级的原因队列需要在队列尾以外的地方插入，开发者可能会选择双链表来实现。在此，我们使用因为数组来实现线性和循环队列。让我们从清单13的Queue接口开始：

// Queue.java

package com.javajeff.cds;

public interface Queue
{
void insert (Object o);
boolean isEmpty ();
boolean isFull ();
Object remove ();
}

Queue声明了四个方法，分别用于在队列中存储数据项，确定队列是否为空，确定队列是否为满，由队列获取或删除数据项。

清单14 给出了基于一维数组的线性队列的实现：

清单14. ArrayLinearQueue.java

// ArrayLinearQueue.java



package com.javajeff.cds;



public class ArrayLinearQueue implements Queue

{

private int front = -1, rear = -1;

private Object[] queue;



public ArrayLinearQueue(int maxElements)

{

queue = new Object[maxElements];

}



public void insert(Object o)

{

if (rear == queue.length - 1)

throw new FullQueueException();



queue[++rear] = o;

}



public boolean isEmpty()

{

return front == rear;

}



public boolean isFull()

{

return rear == queue.length - 1;

}



public Object remove()

{

if (front == rear)

throw new EmptyQueueException();



return queue[++front];

}

}

ArrayLinearQueue表明队列由front，rear和queue变量组成。其中front和rear初始化为－1表示队列为空。与ArrayStack的构造器一样，使用一个说明元素最大数目的整型值调用public ArrayLinearQueue(int maxElements)以创建一个ArrayLinearQueue对象。

当rear说明的是数组的最后一个元素时，ArrayLinearQueue's insert(Object o)方法会抛出FullQueueException异常对象。FullQueueException的代码如清单15所示：

清单 15. FullQueueException.java

// FullQueueException.java

package com.javajeff.cds;

public class FullQueueException extends RuntimeException
{
}

当front等于rear时，ArrayLinearQueue's remove()方法会抛出EmptyQueueException对象。EmptyQueueException的代码如下：

清单16. EmptyQueueException.java

// EmptyQueueException.java

package com.javajeff.cds;

public class EmptyQueueException extends RuntimeException
{
}

清单17 给出了基于一维数组的循环队列的实现：

Listing 17. ArrayCircularQueue.java

// ArrayCircularQueue.java



package com.javajeff.cds;



public class ArrayCircularQueue implements Queue

{

private int front = 0, rear = 0;

private Object[] queue;



public ArrayCircularQueue(int maxElements)

{

queue = new Object[maxElements];

}



public void insert(Object o)

{

int temp = rear;



rear = (reart + 1) ％ queue.length;

if (front == rear)

{

rear = temp;

throw new FullQueueException();

}



queue[rear] = o;

}



public boolean isEmpty()

{

return front == rear;

}



public boolean isFull()

{

return ((rear + 1) ％ queue.length) == front;

}



public Object remove()

{

if (front == rear)

throw new EmptyQueueException();



front = (front + 1) ％ queue.length;



return queue[front];

}

}

从私有域变量和构造器来看，ArrayCircularQueue表明了一个与ArrayLinearQueue类似的实现。insert(Object o)方法令人注意的地方是它在使得rear指向下一个狭槽之前先保存了当前的值。这样，如果循环队列已满，那么rear在FullQueueException异常对象抛出之前恢复为原值。Rear值的还原是必要的，否则front等于rear，后续调用remove()会导致EmptyQueueException异常（即使循环队列不为空）。

在研究了组成队列这一数据结构的基于一维数组的实现的接口和各种类之后，考虑清单18,这是一个说明线性和循环队列的应用程序。

清单 18. QueueDemo.java

// QueueDemo.java

import com.javajeff.cds.*;

class QueueDemo
{
public static void main (String [] args)
{
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");

queueDemo (new ArrayLinearQueue (5));

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

queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}

static void queueDemo (Queue q)
{
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());

System.out.println ("Inserting \"This\"");
q.insert ("This");

System.out.println ("Inserting \"is\"");
q.insert ("is");

System.out.println ("Inserting \"a\"");
q.insert ("a");

System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");

System.out.println ("Inserting \".\"");
q.insert (".");

try
{
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e)
{
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}

System.out.println ();

while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");

try
{
q.remove ();
}
catch (EmptyQueueException e)
{
System.out.println ("One remove too many");
}

System.out.println ();
}
}

运行QueueDemo得到如下输出:

ArrayLinearQueue Demo
---------------------
Is empty = true
Is full = false
Inserting "This"
Inserting "is"
Inserting "a"
Inserting "sentence"
Inserting "."
Inserting "One last item"
One insert too many
Is empty = false
Is full = true

This [Is empty = false, Is full = true]
is [Is empty = false, Is full = true]
a [Is empty = false, Is full = true]
sentence [Is empty = false, Is full = true]
. [Is empty = true, Is full = true]
One remove too many

ArrayCircularQueue Demo
---------------------
Is empty = true
Is full = false
Inserting "This"
Inserting "is"
Inserting "a"
Inserting "sentence"
Inserting "."
Inserting "One last item"
One insert too many
Is empty = false
Is full = true

This [Is empty = false, Is full = false]
is [Is empty = false, Is full = false]
a [Is empty = false, Is full = false]
sentence [Is empty = false, Is full = false]
. [Is empty = true, Is full = false]
One remove too many



树

树是有穷节点的组，其中有一个节点作为根，根下面的其余节点以层次化方式组织。引用其下节点的节点是父节点，类似，由上层节点引用的节点是孩子节点。没有孩子的节点是叶子节点。一个节点可能同时是父节点和子节点。

一个父节点可以引用所需的多个孩子节点。在很多情况下，父节点至多只能引用两个孩子节点，基于这种节点的树称为二叉树。图13给出了一棵以字母表顺序存储了七个String单词的二叉树。


图15 一颗有七个节点的二叉树

在二叉树或其他类型的树中都是使用递归来插入，删除和遍历节点的。出于简短的目的，我们并不深入研究递归的节点插入，节点删除和树的遍历算法。我们改为用清单19中的一个单词计数程序的源代码来说明递归节点插入和树的遍历。代码中使用节点插入来创建一棵二叉树，其中每个节点包括一个单词和词出现的计数，然后藉由树的中序遍历算法以字母表顺序显示单词及其计数。

Listing 19. WC.java

// WC.java

import java.io.*;

class TreeNode
{
String word; // Word being stored.
int count = 1; // Count of words seen in text.
TreeNode left; // Left subtree reference.
TreeNode right; // Right subtree reference.

public TreeNode (String word)
{
this.word = word;
left = right = null;
}

public void insert (String word)
{
int status = this.word.compareTo (word);

if (status > 0) // word argument precedes current word
{
// If left-most leaf node reached, then insert new node as
// its left-most leaf node. Otherwise, keep searching left.

if (left == null)
left = new TreeNode (word);
else
left.insert (word);
}
else
if (status < 0) // word argument follows current word
{
// If right-most leaf node reached, then insert new node as
// its right-most leaf node. Otherwise, keep searching right.

if (right == null)
right = new TreeNode (word);
else
right.insert (word);
}
else
this.count++;
}
}

class WC
{
public static void main (String [] args) throws IOException
{
int ch;

TreeNode root = null;

// Read each character from standard input until a letter
// is read. This letter indicates the start of a word.

while ((ch = System.in.read ()) != -1)
{
// If character is a letter then start of word detected.

if (Character.isLetter ((char) ch))
{
// Create StringBuffer object to hold word letters.

StringBuffer sb = new StringBuffer ();

// Place first letter character into StringBuffer object.

sb.append ((char) ch);

// Place all subsequent letter characters into StringBuffer
// object.

do
{
ch = System.in.read ();

if (Character.isLetter ((char) ch))
sb.append ((char) ch);
else
break;
}
while (true);

// Insert word into tree.

if (root == null)
root = new TreeNode (sb.toString ());
else
root.insert (sb.toString ());
}
}

display (root);
}

static void display (TreeNode root)
{
// If either the root node or the current node is null,
// signifying that a leaf node has been reached, return.

if (root == null)
return;

// Display all left-most nodes (i.e., nodes whose words
// precede words in the current node).

display (root.left);

// Display current node's word and count.

System.out.println ("Word = " + root.word + ", Count = " +
root.count);

// Display all right-most nodes (i.e., nodes whose words
// follow words in the current node).

display (root.right);
}
}

因为已经有很多注释了，在这儿我们就不讨论代码了。代之，建议你如下运行这个应用程序：要计数文件中的单词数，打开一个包括重定位符<的命令行。例如，发出java WC <WC.java命令来计数文件WC.java中的单词数。那个命令的输出如下：

Word = Character, Count = 2
Word = Count, Count = 2
Word = Create, Count = 1
Word = Display, Count = 3
Word = IOException, Count = 1
Word = If, Count = 4
Word = Insert, Count = 1
Word = Left, Count = 1
Word = Otherwise, Count = 2
Word = Place, Count = 2
Word = Read, Count = 1
Word = Right, Count = 1
Word = String, Count = 4
Word = StringBuffer, Count = 5