2.设计包含 min 函数的栈（栈）
定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
我的思路：
用一个额外的元素记录最小值，push时若遇到更小的则更新。但是pop的时候遇到了问题，最小的弹出去了怎么得到下一个最小的值？ 总觉得要排序，再存一个min的链。结果没达到O(1).
/*
2.设计包含 min 函数的栈（栈）
定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
*/
#include <stdio.h>
#include <stdlib.h> typedef int Elemtype; typedef struct Stack_Elem
{
Elemtype data;
Stack_Elem * p_next;
};
typedef struct My_Stack
{
Elemtype min;
Stack_Elem * top;
}My_Stack; Elemtype Stack_Min(My_Stack S)
{
return S.min;
} void Stack_Push(My_Stack* S, Elemtype e)
{
Stack_Elem * new_element = (Stack_Elem *)malloc(sizeof(Stack_Elem));
new_element->data = e;
new_element->p_next = S->top;
S->top = new_element; S->min = (S->min < e) ? S->min : e;
} Elemtype Stack_Pop(My_Stack* S)
{
if(S == NULL)
{
printf("error");
return -;
}
Stack_Elem * pop_elem = S->top;
S->top = pop_elem->p_next;
pop_elem->p_next = NULL;
Elemtype e = pop_elem->data;
if(e == S->min)
{
Elemtype min = S->top->data;
Stack_Elem * p = S->top;
while(p->p_next != NULL)
{
if (p->data < min)
{
min = p->data;
}
p = p->p_next;
}
S->min = min;
} free(pop_elem);
return e;
} int main()
{
My_Stack S;
S.min = ;
S.top = NULL; Stack_Push(&S, );
Stack_Push(&S, );
Stack_Push(&S, );
Stack_Push(&S, );
Stack_Push(&S, ); Elemtype e = Stack_Min(S); e = Stack_Pop(&S);
e = Stack_Pop(&S); e = Stack_Min(S); return ;
}
网上找答案，突然恍然大悟，存一个最小值的栈就好了，每次遇到新的最小值就进栈，不是新最小值就不理会。这样是没问题的，如
栈中元素：3 4 2 5 6 1
min栈中的元素：3 2 1
弹出1后
栈中元素：3 4 2 5 6
min栈中的元素：3 2
弹5 6时不会影响 最小值。
网上代码：http://www.cnblogs.com/likwo/archive/2010/12/21/1912331.html
// minStatck.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <cassert> using namespace std; template<typename T>
class StackSuppliedMin{
public:
vector<T> datas;
vector<size_t> minStack; void push(T data){
datas.push_back(data);
if (minStack.empty() || data < datas[minStack.back()])
minStack.push_back(datas.size()-);
} void pop(){
assert(!datas.empty());
if (datas.back() == datas[minStack.back()])
minStack.pop_back();
datas.pop_back();
} T min(){
assert(!datas.empty() && !minStack.empty());
return datas[minStack.back()];
} void display(){
cout << "datas = ";
for (unsigned i = ; i < datas.size(); i ++)
cout << datas[i] << " ";
cout << endl;
cout << "minStack = ";
for (unsigned i = ; i < minStack.size(); i ++)
cout << datas[minStack[i]] << " ";
cout << endl;
cout << "min = " << datas[minStack.back()] << endl << endl;
}
};
void main()
{
StackSuppliedMin<int> s;
s.push();
s.display();
s.push();
s.display();
s.push();
s.display();
s.push();
s.display();
s.pop();
s.display();
s.pop();
s.display();
s.push();
s.display(); }