iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 4
0

堆疊 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

應用

參考

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


上一篇
[Data Structure][Linked list]
下一篇
[Data Structure][Queue]
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言