使用Java數組實現順序棧

1，首先總結一下線性表（分為順序表和鏈接表，【即順序存儲結構和鏈式存儲結構的區別】）和棧（順序棧和鏈接棧）還有隊列（順序隊列和鏈接隊列）的JAVA類庫中的實現：

java.util.ArrayList 實現了順序表，java.util.LinkedList 實現了鏈接表的功能。

java.util.ArrayDeque實現了順序棧和順序隊列（該類中即定義了與棧操作有關的方法，也定義了與隊列操作有關的方法）、java.util.LinkedList實現了鏈接棧和鏈接隊列。

2，定義了一個Stack<E>接口，指明該棧實現了哪些具體的操作。接口如下：

public interface Stack<E> {
public int length();//返回棧的長度

public E pop();//出棧

public void push(E element);//進棧

public E peek();//訪問棧頂元素

public boolean empty();//判斷棧是否為空

public void clear();//清空棧
}

3，在JAVA類庫中，java.util.ArrayDeque類實現了順序棧的功能。ArrayDeque可以實現動態地擴展棧的大小，但是不支持多線程訪問。同時，ArrayDeque還實現了順序隊列的功能。

4，定義了一個Object[] 類型的數組，用來保存順序棧中的元素。具體實現類SequenceStack.java 如下：

import java.util.Arrays;

public class SequenceStack<E> implements Stack<E> {

private int DEFAULT_SIZE = 16;//定義棧的初始默認長度
private int capacity;//保存順序棧的長度
private int size;//保存順序棧中元素的個數
private Object[] elementData;//定義一個數組用於保存順序棧中的元素

public SequenceStack() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}

//以指定的大小來創建棧
public SequenceStack(int initSize){
capacity = 1;
while(capacity < initSize)
capacity <<= 1;//將capacity設置成大於initSize的最小2次方
elementData = new Object[capacity];
}

//返回當前順序棧中元素的個數
public int length() {
return size;
}

public E pop() {
if(empty())
throw new IndexOutOfBoundsException("棧空，不能出棧");
E oldValue = (E)elementData[size - 1];
elementData[--size] = null;//讓垃圾回收器及時回收，避免內存洩露
return oldValue;
}

public void push(E element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}

private void ensureCapacity(int minCapacity){
if(minCapacity > capacity){
while(capacity < minCapacity)
capacity <<= 1;
elementData = Arrays.copyOf(elementData, capacity);
}
}

//獲取棧頂元素，不會將棧頂元素刪除
public E peek() {
if(size == 0)
throw new ArrayIndexOutOfBoundsException("棧為空");
return (E)elementData[size - 1];
}

public boolean empty() {
return size == 0;
}

public void clear() {
// Arrays.fill(elementData, null);
for(int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

public String toString(){
if(size == 0)
return "[]";
else{
StringBuilder sb = new StringBuilder("[");
for(int i = size - 1; i >= 0; i--)
sb.append(elementData[i].toString() + ", ");
int len = sb.length();
//刪除由於上面for循環中最後添加的多余的兩個字符 (一個是逗號，一個是空格符號)
return sb.delete(len - 2, len).append("]").toString();
}
}
}