剣指offerの面接問題21 min関数を含むスタック

問題の説明:
スタックのデータ構造を定義し、スタックの最小要素を得ることができる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
",getMin(S));
	push(S,3);
	printf("min is :%d
",getMin(S));
	push(S,0);
	printf("min is :%d
",getMin(S));
	pop(S);
	printf("min is :%d
",getMin(S));
	pop(S);
	printf("min is :%d
",getMin(S));
	return 0;
}

参考資料:
剣指オフ
備考:
転載は出典を明記してください.http://blog.csdn.net/wsyw126/article/details/51372294
作者:WSYW 126