剑指offer之面试题21包含min函数的栈

﹏ヽ暗。殇╰゛Y 2022-08-22 03:49 125阅读 0赞

**问题描述**：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push以及pop的时间复杂度都是O(1)。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include<math.h>
    struct StackIn{
    	int array[100];
    	int top;
    };
    typedef struct StackIn StackIn;
    struct Stack{
    	StackIn *stack;
    	StackIn *min_stack;
    };
    typedef struct Stack Stack;
    
    void initStackIn(StackIn *S){
    	S->top=0;
    	S->array[0]=100;
    }
    void pushIn(StackIn *S,int value){
    	S->array[(S->top)++]=value;
    }
    int popIn(StackIn *S){
    	return S->array[--(S->top)];
    }
    
    int getIn(StackIn *S){
    	int i =S->top-1;
    	return S->array[i];
    }
    
    void initStack(Stack *S){
    	S->stack=(StackIn *)malloc(sizeof(struct StackIn));
    	S->min_stack=(StackIn *)malloc(sizeof(StackIn));
    	initStackIn(S->stack);
    	initStackIn(S->min_stack);
    }
    
    void push(Stack *S,int value){
    	int min = getIn(S->min_stack);
    	if(value<min){
    		pushIn(S->min_stack,value);
    	}else{
    		pushIn(S->min_stack,min);
    	}
    	pushIn(S->stack,value);
    }
    int pop(Stack *S){
    	popIn(S->min_stack);
    	return popIn(S->stack);
    }
    int getMin(Stack *S){
    	return getIn(S->min_stack);
    }
    int main(int argc, char *argv[])
    {
    	Stack *S=malloc(sizeof(Stack));
    	initStack(S);
    	push(S,1);
    	printf("min is :%d\n",getMin(S));
    	push(S,3);
    	printf("min is :%d\n",getMin(S));
    	push(S,0);
    	printf("min is :%d\n",getMin(S));
    	pop(S);
    	printf("min is :%d\n",getMin(S));
    	pop(S);
    	printf("min is :%d\n",getMin(S));
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51372294  
作者：WSYW126