设计包含min 函数的栈

定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。要求函数min、push 以及pop 的时间复杂度都是O(1)。

我们定义数据结构如下：

1 struct StackElement
2 {
3     // 存储入栈元素
4     int nData;
5 
6     // 存储栈中最小元素
7     int Min;
8 };

节点中有两个属性，一个存储此节点中的内容，一个存储当前栈中的最小元素。

则push函数代码为：

 1 void Push(StackElement *Stack, int nTop, int nValue)
 2 {
 3     assert (Stack != NULL);
 4 
 5     assert (nTop >= -1);
 6 
 7     if ((-1 == nTop) || (nValue <= Stack[nTop].Min))
 8     {
 9         // 如果在将nValue入栈之前栈是空的，或者nValue比当前栈中的最小元素小
10         // ， 则nValue成为了当前栈中的最小值
11         Stack[++nTop].nData = nValue;
12         Stack[nTop].Min = nValue;
13 
14         return;
15     }
16 
17     Stack[++nTop].nData = nValue;
18 
19     // 如果nValue比当前栈中的最小元素大
20     // ，则说明栈中的最小元素依然是之前的最小元素
21     // ，因此只需之前最小栈的栈顶元素再入一次入栈栈，
22     // ，这样就可以保证最小栈的栈顶元素始终是当前栈中的最小元素
23     Stack[nTop].Min = Stack[nTop - 1].Min;
24 }

那这样Min函数就很好写了，直接获取当前栈顶节点里面Min的内容即可，

编码实现如下：

1 int GetMin(StackElement *Stack, int nTop)
2 {
3     assert (Stack != NULL);
4 
5     assert (nTop >= 0);
6 
7     // 直接返回Stack[nTop].Min即可，时间O(1)
8     return (Stack[nTop].Min);
9 }

Pop函数也是同理：

1 int Pop(StackElement *Stack, int &nTop)
2 {
3     assert (Stack != NULL);
4 
5     assert (nTop >= 0);
6 
7     return (Stack[nTop--].Min);
8 }