时间复杂度为O（1）的q求栈最小值和pop，push操作

题目：对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是O(1)。 

分析：要使pop,push,min都是O(1)，所以肯定要牺牲点空间 

思路：1：在stack的数据结构中加两个个字段，如 

typedef struct { 
int data[MAX]; 

int top; 

int min; 

int second; 

}stack; 

pop,push的时候都去栈顶元素，所以是O(1) 

min的时候取stack的min字段，所以也是O(1) 

每次push的时候进行比较，如果当前push的元素比stack->min小，则用当前元素替换stack->min，用原来的min替换second。如果当前push的元素比stack->min大，但比second小，则用当前元素替换stack->second。于是达到了取min的效果，程序如下 

int push(stack * s,int x){ 

ASSERT(s!=NULL); 

if(s->top>=MAX) 

{ 

printf("Stack overload!"); 

return -1; 

} 

s->data[s->top++]=x; 

if(x < s->min) 

s->min=x; 
else if(x < s->second)
s->second = x;

return 0; 

} 
每次pop的时候进行比较，如果pop的元素为min，则用second替换min。于是达到了取min的效果，程序如下 
int pop(stack *s,int *x) 

{ 

ASSERT(s!=NULL); 

if(s->top<=0) 

{ 

printf("Stack Empty!"); 

return -1; 

} 

(*x) = s->data[s->top--]; 
if(x==s->min)  s->min=s->second; 
return 0; 

} 

int min( stack *s,int *x ) 

{ 

ASSERT(s!=NULL); 

(*x)=s->min; 

return 0; 

} 


思路2：设置辅助栈ass,记录每个状态下的最小值，每次插入时，得到辅助栈当前值，和插入的值比较 

如果小则插入到最小值栈的就是它，否则就是原来的最小值，通过这种方式，pop，push，min三个都是

O(1)算法的。 

typedef struct { 

int data[MAX]; 

int top; 

}stack; 

STATIC int push_stack(stack *s,int x) 

{ 

ASSERT((s!=NULL)); 

if(s->top>=MAX) 

{ 

printf("Stack overload"); 

return -1; 

} 

s->data[s->top++]=x; 

return 0; 

} 

STATIC int pop_stack(stack *s,int *x) 

{ 

ASSERT(s!=NULL); 

if(s->top<=0) 

{ 

printf("Stack Empty"); 

return -1; 

} 

(*x)=s->data[s->top--]; 

return 0; 

} 

int push(stack *main,stack *ass,int x) 

{ 

ASSERT((main!=NULL)&&(ass!=NULL)); 

int temp; 

pop_stack(ass,&temp); 

push_stack(main,x); 

if(x<temp) 

{ 

push_stack(ass,temp); 

push_stack(ass,x); 

} 

else 

{ 

push_stack(ass,temp); 

push_stack(ass,temp); 

} 

return 0; 

} 

int pop(stack *main,stack *ass,int *x) 

{ 

ASSERT((main!=NULL)&&(ass!=NULL)); 

int temp; 

pop_stack(ass,&temp); 

pop_stack(main,x); 

return 0; 

} 

int min(stack *ass,int *x) 

{ 

ASSERT((main!=NULL)&&(ass!=NULL)); 

pop_stack(ass,x); 

push_stack(ass,(*x)); 

return 0; 
}