資料結構之棧（stack）的實作

一、棧

1.定義

1. 棧的英文為(stack)，是一種資料結構
2. 棧是一個先入後出(FILO-First In Last Out)的有序清單。
3. 棧(stack)是限制線性表中元素的插入和删除隻能線上性表的同一端進行的一種特殊線性表。允許插入和删除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。
4. 根據棧的定義可知，最先放入棧中元素在棧底，最後放入的元素在棧頂，而删除元素剛好相反，最後放入的元素最先删除，最先放入的元素最後删除

2.重要操作

（1）入棧

1. 判斷棧是否為已滿，若滿給出提示資訊
2. 若棧有剩餘空間，則将資料壓入棧頂，并将棧頂指針top上移

（2）出棧

1. 判斷棧是否為空棧，若為空棧則不能出棧，需要抛出異常資訊
2. 若棧不為空棧，則取棧頂元素，将棧頂指針top下移

二、代碼實作

/**
 * @author ymy
 * @date 2020/5/11
 *
 * 使用數組模拟棧
 */
public class SeqStack {

    private int maxSize;//棧的容量
    private int top;//棧頂
    private Object [] data;//用來存放資料的區域
    
    public SeqStack(int maxSize){
        top=-1;
        this.maxSize=maxSize;
        data=new Object[maxSize];
    }

    public void push(Object obj){
        if (isFull()){
            System.out.println("棧已滿");
            return;
        }
        data[++top]=obj;
    }

    public Object pop(){
        if (isEmpty()){
            throw new RuntimeException("棧為空");
        }
        return data[top--];
    }

    public boolean isEmpty(){
        return top==-1;
    }

    public boolean isFull(){
        return top==maxSize-1;
    }

}
           

三、測試

測試代碼：

/**
 * @author ymy
 * @date 2020/5/11
 */
public class TestStack {

    public static void main(String[] args) {
        SeqStack stack = new SeqStack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
        System.out.println("===========");
        stack.push(6);
        stack.push(7);
        stack.push(8);
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}
           

運作結果：