使用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();
        }
    }
}