數(shù)據(jù)結(jié)構(gòu)――棧、隊(duì)列和樹(shù)(Java)

2019-11-18 13:44:43

字體：大中小

供稿：網(wǎng)友

　　數(shù)據(jù)結(jié)構(gòu)――棧、隊(duì)列和樹(shù)

開(kāi)發(fā)者可以使用數(shù)組與鏈表的變體來(lái)建立更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。本節(jié)探究三種這樣的數(shù)據(jù)結(jié)構(gòu):棧、隊(duì)列與樹(shù)。當(dāng)給出算法時(shí)，出于簡(jiǎn)練，直接用java代碼。

棧

棧是這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)項(xiàng)的插入和刪除（獲取）都只能在稱(chēng)為棧頂?shù)囊欢送瓿伞Ｒ驗(yàn)樽詈蟛迦氲臄?shù)據(jù)項(xiàng)就是最先要?jiǎng)h除的數(shù)據(jù)項(xiàng)，開(kāi)發(fā)者往往將棧稱(chēng)為L(zhǎng)ILO（last-in, first-out）數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)項(xiàng)壓入（插入）或者彈出（刪除或取得）棧頂。圖13示例了一個(gè)有三個(gè)String數(shù)據(jù)項(xiàng)的棧，每個(gè)數(shù)據(jù)項(xiàng)壓入棧頂。

圖13 有三個(gè)以壓入String數(shù)據(jù)項(xiàng)的棧

如圖13所示，棧在內(nèi)存中是向下建起來(lái)的。對(duì)于每個(gè)數(shù)據(jù)項(xiàng)的壓入，之前棧頂?shù)臄?shù)據(jù)項(xiàng)以及其下面的所有數(shù)據(jù)項(xiàng)都得向下移，當(dāng)要從棧中彈出一個(gè)數(shù)據(jù)項(xiàng)時(shí)，取得棧頂元素并將其從棧中刪除。

棧在許多程序設(shè)計(jì)環(huán)境下非常有用。兩個(gè)非常普通的環(huán)境：

·棧保存返回地址：當(dāng)代碼調(diào)用一個(gè)方法時(shí)，調(diào)用指令后的第一條指令的地址壓入當(dāng)前線程的方法調(diào)用棧的頂端。當(dāng)執(zhí)行被調(diào)用方法的返回指令時(shí)，該地址從棧頂彈出，然后從該地址處繼續(xù)執(zhí)行。假如一個(gè)方法調(diào)用了另一個(gè)方法，棧的LIFO行為模式確保了第二個(gè)方法的返回指令將執(zhí)行轉(zhuǎn)移到第一個(gè)方法，而第一個(gè)方法的返回指令能夠?qū)?zhí)行轉(zhuǎn)移到調(diào)用第一個(gè)方法的代碼的代碼。結(jié)果就是，棧代表被調(diào)用方法“記住了”返回地址。

·棧保存每個(gè)被調(diào)用方法的參數(shù)和局部變量：當(dāng)調(diào)用一個(gè)方法時(shí)，JVM在靠近返回地址處分配內(nèi)存存儲(chǔ)所有被調(diào)用方法的參數(shù)和局部變量。假如方法是個(gè)實(shí)例方法，存儲(chǔ)在棧中的其中一個(gè)參數(shù)是當(dāng)前對(duì)象的引用this。

一般可以使用一維數(shù)組或單鏈表實(shí)現(xiàn)一個(gè)棧。假如使用一維數(shù)組，一個(gè)常命名為top的整型變量保存棧頂數(shù)據(jù)項(xiàng)的索引。類(lèi)似地，一個(gè)常命名為top的引用變量引用單鏈表情形下的棧頂節(jié)點(diǎn)（含有棧頂數(shù)據(jù)項(xiàng)）。

根據(jù)Java's Collections API中發(fā)現(xiàn)的體系結(jié)構(gòu)建模棧的實(shí)現(xiàn)。這個(gè)實(shí)現(xiàn)由一個(gè)Stack接口，ArrayStack和LinkedListStack實(shí)現(xiàn)類(lèi)以及FullStackException支持類(lèi)組成。為了便于發(fā)布，將這些類(lèi)打包在com.javajeff.cds包中，其中的cds表示復(fù)雜數(shù)據(jù)結(jié)構(gòu)。清單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的四個(gè)方法分別是確定棧是否為空，獲得棧頂數(shù)據(jù)項(xiàng)而沒(méi)有刪除，任意數(shù)據(jù)項(xiàng)入棧，獲得并刪除棧頂元素。除了一個(gè)具體于實(shí)現(xiàn)的構(gòu)造方法之外，你的程序只需調(diào)用這些方法就足夠了。

清單9 給出了Stack的基于一維數(shù)組的實(shí)現(xiàn)：

清單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()

上一篇：提升Java桌面客戶(hù)端程序性能

下一篇：數(shù)據(jù)庫(kù)連接池技術(shù)淺析