---
title: 'Stack 堆疊'
disqus: kyleAlien
---

Stack 堆疊
===

## OverView of Content

如有引用參考請詳註出處，感謝 :smile_cat:

> **First in last out** 先進後出，只能從頂端取得資料

[TOC]

## 靜態 Stack
* 靜態 Stack 創建較容易，但是有大小限制，在**創建出來時就必須指定 Stack Size**，但過大可能會浪費資料空間

public class TestStack {

	public static void main(String[] args) {
		
		StaticStack s = new StaticStack(10);
		
		for(int i = 0; i < 12; i++) {
			s.push(i);
		}
		
		for(int i = 0; i < 13; i++) {
			int r = s.pop();
			if(r != -1) {
				System.out.println("pop " + (i+1) + ": " + r);
			}
		}
	}
}

interface StackMethod{
	boolean isEmpty();
	void push(int data);
	int pop();
}

class StaticStack implements StackMethod {
	private int[] Static;
	private int index = -1;
	
	StaticStack(int size) {
		Static = new int[size];
	}
	
	private void hint(String h) {
		System.out.println("Hint: " + h);
	}
	
	boolean isFull() {
		return (index + 1) == Static.length;
	}
	
	@Override
	public boolean isEmpty() {
		return index == -1;
	}

	@Override
	public void push(int data) {
		if(isFull()) {
			hint("Static Stack is Full");
		} else {
			Static[++index] = data;
		}
	}

	@Override
	public int pop() {
		int result = -1;
		if(isEmpty()) {
			hint("Static is empty, cannot pop");
		} else {
			result =  Static[index--];
		}
		
		return result;
	}
}

**--實作--**
> 

## 動態 Stack
* 設計起來較麻煩，但**不限制 Stack 大小**，，依照大小創建，有效利用資料空間

public class TestStack {

	public static void main(String[] args) {
		LinkedStack l = new LinkedStack();
		for(int i = 0; i < 12; i++) {
			l.push(i);
		}
		
		for(int i = 0; i < 15; i++) {
			int r = l.pop();
			if(r != -1) {
				System.out.println("pop " + (i+1) + ": " + r);
			}
		}
	}

}

interface StackMethod{
	boolean isEmpty();
	void push(int data);
	int pop();
}

class Node {
	Node next;
	int index;
	
	Node(int index) {
		this.index = index;
		next = null;
	}
}

class LinkedStack implements StackMethod {
	Node first = null;
	Node last = null;

	private void hint(String h) {
		System.out.println("Hint: " + h);
	}
	
	@Override
	public boolean isEmpty() {
		return first == null;
	}

	@Override
	public void push(int data) {
		Node n = new Node(data);
		
		if(isEmpty()) {
			first = n;
			last = n;
		} else {
			last.next = n;
			last = n;
		}
	}

	@Override
	public int pop() {
		int result = -1;
		if(isEmpty()) {
			hint("Linked List is Empty cannot pop");
		} else {
			if(last == first) {
				result = last.index;
				last = null;
				first = null;
			} else {
				Node temp = first;
				while(temp.next != last) {
					temp = temp.next;
				}
				result = last.index;
				last = temp;
			}
		}
		return result;
	}
	
	
}

**--實作--**
> 

## Stack 使用

### 老鼠走迷宮
* 走過的路放進 Stack 內，如過遇到的不是出口則往回退，退到有另外一條路可走
> 起點是 1, 1
> 未走過的路是 0, 牆壁是 1, 過的路是 2

public class TestMouse {

	public static int ExitX = 8;
	public static int ExitY = 10;
	
	public static int[][] MAZE =  {
			{1,1,1,1,1,1,1,1,1,1,1,1},
			{1,0,0,0,0,0,0,0,0,1,1,1},
			{1,1,1,0,1,1,1,1,0,0,1,1},
			{1,1,1,0,1,0,0,1,1,1,1,1},
			{1,1,1,0,1,0,1,1,0,0,0,1},
			{1,1,0,0,0,0,1,1,1,0,1,1},
			{1,1,0,1,1,1,1,0,0,0,0,1},
			{1,1,0,1,1,1,1,0,1,1,0,1},
			{1,0,0,0,0,0,0,0,1,1,0,1},
			{1,1,1,1,1,1,1,1,1,1,1,1},
	};
	
	public static void main(String[] args) {
		int nowX = 1, nowY = 1;
		
		TraceRoad t = new TraceRoad();
		
		printMaze();

		while(nowX <= ExitX && nowY <= ExitY) {
			MAZE[nowX][nowY] = 2;
			
			if(MAZE[nowX-1][nowY] == 0) {	// upon have road
				nowX -= 1;
				t.push(nowX, nowY);
			} else if(MAZE[nowX][nowY+1] == 0) {	// right have road
				nowY += 1;
				t.push(nowX, nowY);
			} else if(MAZE[nowX+1][nowY] == 0) {	// down have road
				nowX += 1;
				t.push(nowX, nowY);
			} else if(MAZE[nowX][nowY-1] == 0) {	// left have road
				nowY -= 1;
				t.push(nowX, nowY);
			} else if (getExit(nowX, nowY)) {
				System.out.println("Reach Exit");
				break;
			} else {
				t.pop();				// 1 : 
                // 2 :
				nowX = t.last.x;		// Previous x
				nowY = t.last.y;		// Previous y
			}
		}
        
		printMaze();
	}
	
	private static boolean getExit(int x, int y) {
		boolean result = false;
		if(x == ExitX && y == ExitY) {
			result = true;
		}
		return result;
	}
	
	private static void printMaze() {
		for(int i = 0; i < MAZE.length; i++) {
			for(int j = 0; j < MAZE[i].length; j++) {
				System.out.print(MAZE[i][j]);
			}
			System.out.println();
		}
	}
}
class XyNode {
	XyNode next;
	int x, y;
	
	XyNode(int x, int y) {
		this.x = x;
		this.y = y;
		next = null;
	}
}

class TraceRoad {
	XyNode first = null;
	XyNode last = null;

	private void hint(String h) {
		System.out.println("Hint: " + h);
	}
	
	public boolean isEmpty() {
		return first == null;
	}

	public void push(int x, int y) {
		XyNode n = new XyNode(x, y);
		
		if(isEmpty()) {
			first = n;
			last = n;
		} else {
			last.next = n;
			last = n;
		}
	}

	public XyNode pop() {
		XyNode result = null;
		
		if(isEmpty()) {
			hint("Linked List is Empty cannot pop");
		} else {
			if(last == first) {
				result = last;
				last = null;
				first = null;
			} else {
				XyNode temp = first;
				while(temp.next != last) {
					temp = temp.next;
				}
				result = last;
				last = temp;
			}
		}
		return result;
	}
}

> 確認順序是
> > 1. 上右下左
> > 2. 是否是出口
> > 3. 走道盡頭但還不是出口，則往回退
* 1 : 退回到上一步(**pop 後 last 值就會變動**)
* 2 : 使用 pop 後的 last 找回上一步的 X & Y，繼續再找下一條路

**--實作--**
> 搜尋順序是上、右、下、左 所以可以看到圖片中有一個 0 未走過
>
> 
>

### 八皇后
* 皇后的棋子點往 8 個方向延伸都不能碰到其他的皇后
* 以下是參考範例

public class EightQueen {
	
	static int[] queen = new int[8];
	static int number = 0;
	
	public static void printTable() {
		int x = 0, y = 0;
		number+=1;
		System.out.println("Number " + number + " Answer");
		for(x = 0; x < 8; x++) {
			for(y = 0; y < 8; y++) {
				if(x == queen[y]) {
					System.out.print("<*>");
				} else {
					System.out.print("<->");
				}
			}
			System.out.println();
		}
	}
	
	public static boolean attack(int row, int col) {
		boolean atk = false;
		int i = 0;
		int offset_col = 0, offset_row = 0;
		
        //"2: "
		while(!atk && i < col) {
        //"1: "
			offset_col = Math.abs(i - col);
			offset_row = Math.abs(queen[i] - row);
			
			if((offset_col == offset_row) || queen[i] == row) {
				atk = true;
				break;
			}
			i++;
		}
		
		return atk;
	}
	
	public static void decidePosition(int value) {
		int i = 0;
		while(i < 8) {
			if(!attack(i, value)) {
				queen[value] = i;
				if(value == 7) {
					printTable();
				} else {
					decidePosition(value + 1);
				}
			}
			i++;
		}
	}
	
	public static void main(String[] args) {
		decidePosition(0);
	}

}

1. 兩個條件判斷是否衝突，符合其中一個就衝突
> a. 計算其斜率，也就是對角線 tan 45*
> b. 設定座標已在同行(橫向)
2. i < col 代表 queen[i] 的答案只到 i 個，也就是不能超過第幾列(直向)

**--實作--**
> 

## 算術運算式的求值
* 一般人類計算是使用中序法，需要處理**兩種問題**
> Ex: 1+(2\*3+3*3) /3
> > 優先權 : (2\*3+3*3) 中先運算，再算 / 3，再算 +1
> > 結合性 : 左到右

* 運算式是由`運算子`(+, -, *, /) and `運算元`(1, 2, 3, 4...) 組成
* 由於在電腦計算時，處理中序法較不方便，所已改用後續法 or 前序法

### 中序法(infix)
* 必須考慮括號 & 優先權
* **需要兩個堆疊**，一個放運算元，一個放運算子
:::info
範例 : 3 + 1
<運算元1> <運算子> <運算元2>
:::
1. 建立兩個堆疊，一個運算子，一個運算元
2. 在**放入運算子時要先比較堆疊頂端運算子的優先權**，若堆疊頂端運算子優先較高，則先取出運算
3. 取出 2 個運算元 + 一個運算子，算完後再放入堆疊
4. 再比對頂端運算子，如果優先權 <= 要放入的運算子則放入
5. 以此類推，至放置完，再依序取出運算 (先取運算元再取運算符號)
> Ex: 1+2\*9-5\*2
> 1. 先放入 1 + 2
> > 
> 2. 比較運頂層運算子優先順序 再放入乘 (\* 的優先權比 + 高，所以不用取出運算)
> > 
> 3. 放入減號，發現優先權較低，取出先運算 2\*9，再放入減號，跟 5
> > 
> 4. 全部放入
> > 
>
> 依序取出 : (2 * 5) 再取出 -，再放入運算元內，也就是 18 - 2\*5，依此類推最後 + 1
> > 

### 前序法(prefix)
* 不須考慮括號 & 優先權，**++只需要一個堆疊++**
:::info
範例 : 3 + 1
<運算子> <運算元1> <運算元2>
轉換 : +31
:::
1. 取出堆疊元素
2. 遇到運算子則取出 2 個元素跟 1 個運算子，運算完放回堆疊
3. 以此類推

### 後續法(posfix)
* **後運算式可以直接在電腦中運行**
:::info
範例: 3 + 1
<運算元1> <運算元2> <運算子>
轉換 : 31+
:::
1. 直接讀取運算子，遇到運算元，則計算後再放入堆疊
2. 以此類推

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`