堆疊 Stack

今天讀到的資料結構是堆疊 stack，在現實生活中的例子有堆積如山的書堆，或是將洗好的的盤子推成一疊，當要拿書或是拿新盤子的時候，從最頂端拿取才不會造成倒塌，當然在生活中，只要注意不倒塌，還是可以從書堆或盤堆中間取出書或是盤子，但資料結構的堆疊是不行的。

後進先出 Last in first out

我們可以將Stack想像成一個裝東西的箱子，只能從箱子上面把資料放進去，資料會越堆越高，先放進去的資料會在底層，所以就會比較晚被拿出來。後面放進去的資料，因為在比較上層，所以能先行從資料堆拿出來。
這就是一種後進先出 (LIFO) 的資料結構。

功能

• Push -
  將新資料放入堆疊的頂端 Top
  將書疊在最上層
• Pop -
  從堆疊頂端拿走一個資料
  從書堆最上層拿走一本書
• TopItem -
  紀錄堆疊頂端的項目
  紀錄書堆最上面的書籍
• IsEmpty -
  判斷堆疊裡面是否有東西
  空-True、有東西-False
• IsFull -
  判斷堆疊是否滿了
  滿-True、未滿-False

實作

• 測試 push 和 pop:

import java.util.Stack;

public class stack_test 
{
	public static void main(String[] args) 
	{
        // Creating a Stack
        Stack<Double> student_score = new Stack<Double>();

        // Pushing the scores of student to the Stack
        student_score.push(50.0);
        student_score.push(64.0);
        student_score.push(88.0);
        
        System.out.println("Score_Stack -> " + student_score);
        System.out.println("-----------------------------------");

        // Popping scores from the Stack
        Double pop_test = student_score.pop();  
        System.out.println("Pop -> " + pop_test);
        System.out.println("Current Score_Stack -> " + student_score);
    }
}

輸出結果:

Score_Stack -> [50.0, 64.0, 88.0]
-----------------------------------
Pop -> 88.0
Current Score_Stack -> [50.0, 64.0]

• 計算3位學生的數學成績:

import java.util.Stack;

public class stack_test 
{
	public static void main(String[] args) 
	{
        // Creating a Stack
        Stack<Double> student_score = new Stack<Double>();

        // Pushing the scores of student to the Stack
        student_score.push(50.0);
        student_score.push(64.0);
        student_score.push(88.0);
        
        System.out.println("Score_Stack -> " + student_score);

        Double sum = 0.0;
        int stack_size = student_score.size();
        
        // Operating
        while(student_score.isEmpty()!= true)
        {
        	Double pop_num = student_score.pop();
        	sum = sum + pop_num;
        }
        
        Double average = sum / stack_size;
        
        System.out.print("average:" + average);
    }
}

輸出結果:

Score_Stack -> [50.0, 64.0, 88.0]
average:67.33333333333333

應用

• 遞迴
• 深度優先搜尋(DFS)
• 副程式的呼叫與返回
• 運算式的轉換

參考

細談資料結構 第六版
ISBN 978-986-312-014-8