###### tags: `apcs` `解題筆記` `歷屆練習` `自主學習`
{%hackmd BJrTq20hE %}
堆疊Stack題型練習
===
[TOC]
## 堆疊
後進先出的儲存資料方式，適合一些累積後取頭的題型，用Java的ArrayList實作，從尾部取值

ArrayList<Integer> mystack = new ArrayList<>();
mystack.add(1);
mystack.add(2);
mystack.add(3);
while(mystack.size() != 0) {
    System.out.println(mystack.get(mystack.size()-1));
    mystack.remove(mystack.size()-1);
}

## [APCS歷屆:函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)
用堆疊儲存算式，遇到函示名稱的時候取對應需要的參數運算再放回

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class zj_f640 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] d = (br.readLine()).split(" ");
		ArrayList<Integer>list = new ArrayList<>();
		for(int i = d.length - 1;i >= 0;i --) {
			//數字放入堆疊
			if(!d[i].equals("f") && !d[i].equals("g") && !d[i].equals("h")) {
				list.add(Integer.parseInt(d[i]));
			}
			//f(x)取最上面的一個數運算放回
			else if(d[i].equals("f")) {
				int x = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				list.add(f(x));		
			}
			//g(x,y)取最上面兩個數運算放回
			else if(d[i].equals("g")) {
				int x = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				int y = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				list.add(g(x,y));
			}
			//h(x,y,z)取最上面三個數運算放回
			else {
				int x = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				int y = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				int z = list.get(list.size() - 1);
				list.remove(list.size() - 1);
				list.add(h(x,y,z));
			}
		}
		//輸出堆疊裡剩下的數
		System.out.println(list.get(0));
	}
	//函數
	public static int f(int x) {
		return 2 * x - 3;
	}
	public static int g(int x,int y) {
		return 2 * x + y - 7;
	}
	public static int h(int x,int y,int z) {
		return 3 * x - (2 * y) + z;
	}
}