Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
class MinStack {
public:
MinStack(){
capcity=2;
data = new int[capcity];
size=0;
minCapcity=2;
min = new int[minCapcity];
minSize = 0;
}
~MinStack(){
delete[] data;
delete[] min;
}
void push(int x) {
if(size>=capcity){
int* p=data;
capcity = 2*capcity;
data=new int[capcity];
std::memcpy(data, p, sizeof(int)*size);
delete[] p;
}
data[size++]=x;
if(minSize==0){
min[minSize++]=x;
}else if(min[minSize-1]>=x){
if(minSize>=minCapcity){
int* p=min;
minCapcity = 2*minCapcity;
min = new int[minCapcity];
std::memcpy(min, p, sizeof(int)*minSize);
delete[] p;
}
min[minSize++]=x;
}
}
void pop() {
if(size>0){
size--;
if(data[size]==min[minSize-1]){
minSize--;
}
}else{
throw exception();
}
}
int top() {
if(size>0){
return data[size-1];
}else{
throw exception();
}
}
int getMin() {
return min[minSize-1];
}
private:
int size;
int capcity;
int* min;
int minSize;
int minCapcity;
int* data;
};[LeetCode] Min Stack Min Stack
原文:http://blog.csdn.net/kangrydotnet/article/details/44968293