資料結構-棧（一）數組模拟棧的實作

一.棧的概念

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和删除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。（來源于百度百科）

對上述的概念進行總結得到棧的幾個特征

• 棧是線性表，但是棧的操作是受限的
• 對棧的操作應該遵循先進後出，後進先出的規律
• 允許插入删除的一段成為棧頂(top)
• 固定的一段成為棧底(botton)

  

  棧的應用場景：
• 子程式調用，堆棧
• 遞歸調用
• 表達式的轉換（中綴表達式，字尾表達式）
• 二叉樹的周遊
• 圖形深度優先搜尋算法

二.數組模拟棧思路分析

1.定義一個top來表示棧頂，初始化值為-1

• 入棧的操作，當有資料入棧時，top ++; stack[top] = data;

  

• 出棧的操作，先使用變量取值int value = stack[top]，然後top–；

  

三.代碼實作

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        //建立棧對象
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("show：顯示棧");
            System.out.println("push：入棧");
            System.out.println("pop：出棧");
            System.out.println("exit：退出");
            key = scanner.next();
            switch (key){
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("輸入一個數");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出棧的資料是：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
            }
        }
    }
}


//定義一個類表示棧結構
class ArrayStack{
    /*
    棧的大小
     */
    private int maxSize;
    /*
    數組，數組模拟棧，資料就放在該數組
     */
    private int[] stack;
    /*
    top表示棧頂，初始化-1
     */
    private int top = -1;

    /**
     * 構造器，初始化數組
     * @param maxSize
     */
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    /**
     * 棧滿判斷
     */
    public boolean isFull(){
        return top == maxSize - 1;
    }

    /**
     * 棧空
     */
    public boolean isEmpty(){
        return top == -1;
    }

    /**
     * 入棧-push
     */
    public void push(int value){
        //先判斷棧滿
        if(isFull()){
            System.out.println("棧已滿");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出棧-pop
     */
    public int pop(){
        //先判斷棧是否為空
        if(isEmpty()){
            //抛出異常
            throw new RuntimeException("棧空，沒有資料");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 周遊棧,周遊時，需要從棧頂開始顯示資料
     */
    public void list(){
        if(isEmpty()){
            System.out.println("棧空，沒有資料");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

           

歡迎通路我的個人部落格