棧定義
棧是一種基于后進(jìn)先出（LIFO）策略的集合類型贬蛙。本章討論如何使用Java語言實(shí)現(xiàn)一個基本的棧锦亦。一個棧容器要求提供入棧操作马绝，出棧操作择示，獲取棧大小和判斷棧是否為空操作束凑。抽象數(shù)據(jù)類型可定義為：
public interface Stack<Item> {
/*
* 判斷棧是否為空。
*/
public boolean isEmpty();
/*
* 獲取棧大小栅盲。
*/
public int size();
/*
* 入棧汪诉。
*/
public void push(Item item);
/*
* 出棧。
*/
public Item pop();
}
數(shù)組實(shí)現(xiàn)
棧元素存儲在數(shù)組中是一種基本的實(shí)現(xiàn)方式谈秫。內(nèi)部定義一個數(shù)組[]a用于存在入棧的元素扒寄，整數(shù)N保存當(dāng)前元素?cái)?shù)量。
public class ArrayStack<Item> implements Stack<Item> {
/**
* 存儲棧元素
*/
private Item[] a = (Item[]) new Object[1];
/**
* 棧元素?cái)?shù)量
*/
private int N;
@Override
public boolean isEmpty() {
return N == 0;
}
@Override
public int size() {
return N;
}
@Override
public void push(Item item) {
a[N++] = item;
}
@Override
public Item pop() {
Item item = a[--N];
a[N] = null;
return item;
}
}
選擇用數(shù)組標(biāo)示棧內(nèi)容必須先預(yù)估棧最大容量大小拟烫。在Java中该编，數(shù)組一旦創(chuàng)建，其大小就不能改變硕淑。在實(shí)際應(yīng)用中课竣，我們一般無法在創(chuàng)建棧時確定其大小。如果太小喜颁，會導(dǎo)致數(shù)組越界稠氮，如果太大，則會浪費(fèi)內(nèi)存空間半开。因此隔披，我們需要在入棧和出棧中動態(tài)的調(diào)整數(shù)據(jù)大小。
入棧時通過檢查棧大小N和數(shù)組大小a.length是否相等來檢查是否能夠容納新的元素寂拆。如果沒有多余的空間奢米，將數(shù)組的的長度加倍。
出棧時檢查棧大小是否小于數(shù)組的四分之一纠永，如果滿足則把數(shù)組大小減半鬓长。
public class ResizingArrayStack<Item> implements Stack<Item> {
private Item[] a = (Item[]) new Object[1];
private int N = 0;
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void push(Item item) {
if (N == a.length) {
resize(2 * a.length);
}
a[N++] = item;
}
private void resize(int max) {
Item[] temp = (Item[]) new Object[max];
System.arraycopy(a, 0, temp, 0, N);
a = temp;
}
public Item pop() {
Item item = a[--N];
a[N] = null; // 避免對象游離
if (N > 0 && N == a.length / 4) {
resize(a.length / 2);
}
return item;
}
public static void main(String[] args) {
ResizingArrayStack<String> stack = new ResizingArrayStack<>();
stack.push("ye");
stack.push("c");
stack.push("l");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
數(shù)組實(shí)現(xiàn)的缺點(diǎn)在于某些push()和pop()操作會調(diào)整數(shù)組的大小：這項(xiàng)操作的耗時和棧大小成正比尝江。為了克服這個缺點(diǎn)涉波，可以采用鏈表實(shí)現(xiàn)棧。
鏈表實(shí)現(xiàn)
鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空啤覆，或者指向一個節(jié)點(diǎn)的引用苍日，該節(jié)點(diǎn)含有一個泛型的元素和一個指向另一個鏈表的結(jié)構(gòu)。
節(jié)點(diǎn)的抽象數(shù)據(jù)類型可以表示為：
private class Node{
/**
* 存儲數(shù)據(jù)
*/
Item item;
/**
* 下一個節(jié)點(diǎn)引用
*/
Node next;
}
鏈表實(shí)現(xiàn)時用一個節(jié)點(diǎn)表示棧頂元素窗声，整數(shù)N記錄棧大小相恃。入棧時新節(jié)點(diǎn)的下一個節(jié)點(diǎn)引用指向原來的棧頂節(jié)點(diǎn)，出棧時棧頂元素指向原來?xiàng)ｍ斣氐南乱粋€節(jié)點(diǎn)笨觅。
public class LinkedStack<Item> implements Stack<Item> {
/**
* 棧頂
*/
private Node first;
/**
* 元素?cái)?shù)量
*/
private int N;
private class Node {
Item item;
Node next;
}
@Override
public boolean isEmpty() {
return first == null; // or N == 0;
}
@Override
public int size() {
return N;
}
@Override
public void push(Item item) {
// 棧頂添加元素
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
@Override
public Item pop() {
// 棧頂刪除元素
Item item = first.item;
first = first.next;
N--;
return item;
}
}
在結(jié)構(gòu)化存儲數(shù)據(jù)集時拦耐，鏈表是數(shù)組的一種重要替代方式。它們各有優(yōu)點(diǎn)和缺點(diǎn)见剩，我們應(yīng)該根據(jù)實(shí)際情況選擇合適的實(shí)現(xiàn)杀糯。
