# 棧
> 限定在表尾進行插入或刪除操作的線性表。
和隊列先進先出（First In First Out）剛好相反，棧遵循后進先出（Last In First Out）的原則。
- 順序棧：順序存儲結構實現的棧
- 鏈棧：采用鏈式存儲結構實現的棧
### 棧與遞歸
解決問題
- 階乘
- 二階 Fibonacci （斐波那契）數列
- 漢諾塔問題
- 括號匹配
#### 斐波那契數列
數列：1, 1, 2, 3, 5, 8, 13, 21...
規律：后一項是前兩項之和。
F(n) = n; n = 0,1
F(n) = F(n-1) + F(n-2),n >= 2;
常規解法
```php
function fibonacci(n)
{
if (n === 1 || n === 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
```
問題：假設計算 fibonacci(10)，會計算 fibo(9) + fibo(8)，分治分別計算 fibo(9) 和 fibo(8) 時，fibo(8) 會造成重復計算，影響性能。
優化方式一：記錄已計算的項
```php
function fibonacci(&$arr, $k) {
if ($k === 1 || $k === 2) {
return 1;
}
if (isset($arr[$k])) {
return $arr[$k];
}
$arr[$k] = fibonacci($arr, $k-1) + fibonacci($arr, $k-2);
return $arr[$k];
}
```
優化方式二：a[n] = a[n-1] + a[n-2]，本質上只需要記錄最近前兩項即可，相比優化方式一，節省內存
```php
function fibonacci($k) {
$arr = [1, 1];
for ($i = 3; $i <= $k; $i++) {
$temp = $arr[0] + $arr[1];
[$arr[0], $arr[1]] = [$arr[1], $temp];
}
return $arr[1];
}
```
