數據結構――棧、隊列和樹(Java)

2019-11-18 13:44:43

字體：大中小

來源：轉載

供稿：網友

　　數據結構――棧、隊列和樹

開發者可以使用數組與鏈表的變體來建立更為復雜的數據結構。本節探究三種這樣的數據結構:棧、隊列與樹。當給出算法時，出于簡練，直接用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()

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

下一篇：數據庫連接池技術淺析