【25】實作一個含有min函數的棧的通用模闆

題目：設計一個棧類型，使得在該棧類型中有一個函數min可以得到棧的最小元素，要求這個棧的push、pop、min都是O(1)。

分析：

1. 棧的性質是先進後出，是以一般情況下棧的push、pop的時間是O(1)，但是要求棧的min必須要枚舉整個棧，時間複雜度為O(n)

2. 題目要求設計一個棧在O(1)的時間内找到min，我們要想到一個方法來滿足，先看一個例子

3. 從下面的表中我們可以很清楚的看到，我麼需要維護一個儲存min的棧，并且這個棧和我們的資料棧是一起變化的，是以我們可以利用兩個棧來模拟實作這個過程

操作

棧的元素（左邊棧頂）

最小值

第一次

Push 5

5

第二次 

Push 6

6 5

第三次

Push 4

4 6 5

4

第四次

Push 7

7 4 6 5

第五次

Push 9

9 7 4 6 5

第六次

Pop

第七次

第八次

第九次

4. 示例代碼