資料結構：棧
- 棧的定義
- 棧的資料結構
-
- 棧的順序存儲結構
- 棧的鍊式存儲結構
- JAVA中的棧
- 棧的應用
棧的定義
棧是一種隻能在表尾進行插入或者删除操作的線性表。
允許插入和删除的一端叫棧頂，另一端叫棧底，無任何元素叫空棧（空表），是一種先入後出的線性表。
棧的插入操作叫進棧，也有叫壓棧、入棧。（如圖）
棧的删除操作叫出棧，也有叫彈棧。（如圖）
棧的資料結構
棧的順序存儲結構
棧的順序存儲結構也是線性表的存儲結構，可以用數組實作。
public class ArrayStack<T> {
private int DEFAULT_SIZE = 5;//預設大小
private Object[] objs;
private int topIndex = 0;//用來紀錄目前棧頂的下标
public ArrayStack(int DEFAULT_SIZE) {
this.DEFAULT_SIZE = DEFAULT_SIZE;
objs = new Object[DEFAULT_SIZE];
}
public ArrayStack() {
objs = new Object[DEFAULT_SIZE];
}
/**
* 進棧
* @param t 進棧元素
*/
public void push(T t) {
//表示目前數組已經沒有多餘空間(要擴容)
if (topIndex > DEFAULT_SIZE - 1) {
objs = AddSize(objs, DEFAULT_SIZE / 2);
}
objs[topIndex] = t;
topIndex++;
}
/**
* 出棧
* @return true 表示出棧成功，false表示棧為空，出棧失敗
*/
public boolean pop() {
if (topIndex < 0) {
return false;
}
//清空棧頂
objs[topIndex--] = null;
return true;
}
/**
* @param objs 表示要擴容的數組
* @param size 表示要數組要增加多大
* @return 傳回擴容後的新數組
*/
private Object[] AddSize(Object[] objs, int size) {
int newSize = objs.length + size;
Object[] newObj = new Object[newSize];
System.arraycopy(objs, 0, newObj, 0, objs.length);
return newObj;
}
}
| 優點 | 缺點 |
|---|---|
| 存取定位友善 | 需要提前配置設定空間，當空間不足時則需要擴容，影響性能，如果不擴容就會造成溢出 |
棧的鍊式存儲結構
棧的鍊式存儲結構可以用線性表的鍊式存儲結構來實作。
public class LinkStack<T> {
//表示棧的大小
private int size;
//棧頂元素
private Node top;
private class Node<T> {
private Node next;//存放後繼節點
private T data;//資料域
public Node(T data, Node next) {
this.next = next;
this.data = data;
}
public Node() {
}
}
/**
* 入棧
* @param data
*/
public void push(T data) {
top = new Node<>(data, top);
size++;
}
/**
* 出棧
* @return
*/
public T pop() {
if (top == null) {
return null;
}
Node<T> node = top;
top = top.next;
node.next = null;
size--;
return node.data;
}
}
| 優點 | 缺點 |
|---|---|
| 不用提前申請空間，動态配置設定存儲空間 | 因為多了存放指針的操作，會額外增加記憶體 |
總結：如果棧的元素數量固定，建議用鍊式存儲結構，而元素數量變化不定，則建議用鍊式存儲結構。
JAVA中的棧
JDK封裝了Stack的類。位于java.util的包名下。
package java.util;
public class Stack<E> extends Vector<E> {
/**
* 無參的構造函數
*/
public Stack() {
}
/*
* 壓棧
*/
public E push() {
//壓棧
addElement(item);
//傳回壓入棧中的元素
return item;
}
/**
* 出棧
*/
public synchronized E pop() {
E obj;
int len = size();
//擷取棧頂的元素
obj = peek();
//把棧頂元素置為空，并把可用數組長度減一
removeElementAt(len - 1);
return obj;
}
}
主要看壓棧的方法 addElement：
//這是個線程安全的方法
public synchronized void addElement(E obj) {
modCount++;
//擴容
ensureCapacityHelper(elementCount + 1);
//壓棧給棧頂指派 lementData為vector的object[]數組
elementData[elementCount++] = obj;
}
比較複雜的是擴容的方法ensureCapacityHelper：
private void ensureCapacityHelper(int minCapacity) {
// 如果目前棧中的元素再加一比elementData的數組長度大，則需要擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//傳入實際棧的數量
private void grow(int minCapacity) {
// 先把舊的數組長度指派給oldCapacity
int oldCapacity = elementData.length;
//capacityIncrement 為自定義要增加的長度（擴容因子），沒有設定則預設為0，stack沒有設定這個變量，這裡數組的長度為newCapacity =oldCapacity +oldCapacity .
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果新産生的數組長度小于實際需要的數組長度，則使用實際長度。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新産生的數組長度大于 Integer.MAX_VALUE - 8 則等于Integer.MAX_VALUE 或 者Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//真正在這裡擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.copyOf方法：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
//拿到數組類型，并建立newLength長度的數組。
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//把original的數組從0開始，複制到名為copy，下标為0開始的新數組上，到original數組長度跟newLength的最小值的地方（一般都是original.length）。
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//傳回帶有中繼資料的新數組
return copy;
}
出棧方法 pop()調用了peek()與removeElementAt()
先看peek()
public synchronized E peek() {
//擷取棧中元素數量
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
//直接傳回數組下标為index的元素
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
再看出棧的主要方法removeElementAt：
public synchronized void removeElementAt(int index) {
//計數器加1
modCount++;
//如果下标大于數組總長度抛異常
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
//如果下标為負數抛異常
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
//擷取需要複制數組元素的個數（用可用的數組減去棧頂的下标再減一，減一是因為下标是從0開始）
int j = elementCount - index - 1;
if (j > 0) {
//重新構造數組，這裡主要是移除非棧頂的元素，棧沒有用到。
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//有效數量鍵1
elementCount--;
//清空數組中最後一個元素清空
elementData[elementCount] = null; /* to let gc do its work */
}
可以看到java提供的棧stack用了線性表的順序存儲結構。
java提供的stack可以直接使用，不用關心棧溢出問題，調用stack的push()、pop(),就可以進行入棧出棧操作。
但有一個缺點是當Stack快速入棧多個元素後再恢複回來，在元素不變的前提下，其實elementCount數組的長度會增加，這個數組會一直占有着記憶體，造成記憶體浪費。
棧的應用
- Android中的atcivity棧。
- 遞歸函數（如斐波那契數列的實作）。
- 四則運算中的中綴表達式與字尾表達式的計算。
參考：大話資料結構
下一節 資料結構：隊列