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

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

自己用c语言编写的一个程序，是按照数据结构书上给出的结构。如果不对的地方请指教。同时会给出c++的设计。

#include<stdio.h>
#include<stdlib.h>
#define STACK_MAX_CAPACITY 20
#define INCREMENT 10
typedef struct stack{
	int *base;
	int *top;
	int capacity;
}stack;
stack data_stack;
stack min_stack;
void init_stack(stack *s){
	(*s).base = (int *)malloc(sizeof(int)*STACK_MAX_CAPACITY);
	(*s).top = (*s).base;
	(*s).capacity = STACK_MAX_CAPACITY;
}
void push(int e) {
	if((data_stack.top - data_stack.base) >= data_stack.capacity)
		data_stack.base = (int*)realloc(data_stack.base, sizeof(int)*(STACK_MAX_CAPACITY + INCREMENT));
	if(!data_stack.base)
		return;
	data_stack.capacity += INCREMENT;
	*data_stack.top++ = e;
	if((min_stack.top - min_stack.base) >= min_stack.capacity)
		min_stack.base = (int*)realloc(min_stack.base, sizeof(int)*(STACK_MAX_CAPACITY + INCREMENT));
	if(!min_stack.base)
		return;
	data_stack.capacity += INCREMENT;
	if(min_stack.top == min_stack.base) {
		*min_stack.top++ = e;
	} else {
		if(e <= *(min_stack.top - 1))
			*min_stack.top++ = e;
	}
}
void pop(int *e){
	if(data_stack.top == data_stack.base)
		return;
	*e = *(--data_stack.top);
	if(*e <= *(min_stack.top - 1))
		min_stack.top--;
}
void min(int *min_data) {
	if(min_stack.top == min_stack.base)
		return;
	*min_data = *(min_stack.top - 1);
}
void main() {
	int min_data;
	int pop_data;
	init_stack(&data_stack);
	init_stack(&min_stack);
	push(3);
	min(&min_data);
	printf("min data=%d\n",min_data);
	push(4);
	min(&min_data);
	printf("min data=%d\n",min_data);
	push(2);
	min(&min_data);
	printf("min data=%d\n",min_data);
	push(1);
	min(&min_data);
	printf("min data=%d\n",min_data);
	pop(&pop_data);
	min(&min_data);
	printf("pop data=%d,min data:%d\n",pop_data,min_data);
	pop(&pop_data);
	min(&min_data);
	printf("pop data=%d,min data:%d\n",pop_data,min_data);
	pop(&pop_data);
	min(&min_data);
	printf("pop data=%d,min data:%d\n",pop_data,min_data);
	push(0);
	min(&min_data);
	printf("min data:%d\n",min_data);
}

c++代码，我是用vector实现的，但是看到网上还是有高手用到双端队列，我也会试着用双端队列实现一下的，自己写的这两个程序基本没什么大的改变，大家可以用另一种思路，就是记录最小元素的位置。

#include<iostream>
#include<vector>
using namespace std;
class StackWithMin{
private:
	vector<int> m_data;
	vector<int> min_data;
public:
	StackWithMin() {
	}
	~StackWithMin() {
		while(m_data.size() > 0)
			m_data.pop_back();
		while(min_data.size() > 0)
			min_data.pop_back();
	}
	void push(int e) {
		m_data.push_back(e);
		if(min_data.size() == 0) {
			min_data.push_back(e);
		} else {
			if(e <= min_data.back())
				min_data.push_back(e);
		}
	}
	void pop(int *e) {
		if(m_data.size() > 0) {
			*e = m_data.back();
			m_data.pop_back();
			if(*e <= min_data.back())
				min_data.pop_back();
		} else {
			cout << "error,no elements" << endl;
		}
	}
	void min(int *min) {
		if(min_data.size() > 0){
			*min = min_data.back();
		} else {
			cout << "error,no elements" << endl;
		}
	}
};
int main() {
	int min_data;
	int pop_data;
	StackWithMin m_stack;
	m_stack.push(3);
	m_stack.min(&min_data);
	cout << "min_data=" << min_data << endl;
	m_stack.push(4);
	m_stack.min(&min_data);
	cout << "min_data=" << min_data << endl;
	m_stack.push(2);
	m_stack.min(&min_data);
	cout << "min_data=" << min_data << endl;
	m_stack.push(1);
	m_stack.min(&min_data);
	cout << "min_data=" << min_data << endl;
	m_stack.pop(&pop_data);
	m_stack.min(&min_data);
	cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;
	m_stack.pop(&pop_data);
	m_stack.min(&min_data);
	cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;
	m_stack.pop(&pop_data);
	m_stack.min(&min_data);
	cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;
	m_stack.push(0);
	m_stack.min(&min_data);
	cout << "min_data=" << min_data << endl;
	return 0;
}