155.c

#include<stdio.h>
#include<stdlib.h>

typedefstructStackNode {
intval;
structStackNode*next;
} StackNode;

typedefstructMinStack {
intsize;
StackNode*top;
StackNode*min;
} MinStack;

voidminStackCreate(MinStack*stack, intmaxSize) {
/* I implement a linked stack, so I don't need maxSize */
if (stack) {
stack->min=NULL;
stack->top=NULL;
stack->size=0;
 }
}

voidminStackPush(MinStack*stack, intelement) {
if (stack) {
StackNode*new_node= (StackNode*)calloc(1, sizeof(StackNode));
new_node->val=element;
new_node->next=stack->top;
stack->top=new_node;
stack->size++;
/* update min pointer */
StackNode*new_min= (StackNode*)calloc(1, sizeof(StackNode));
new_min->val=element;
new_min->next=stack->min;

if (stack->min) {
if (stack->min->val >= element){
stack->min=new_min;
 }
 }
else {
stack->min=new_min;
 }
 }
}

voidminStackPop(MinStack*stack) {
if (stack&&stack->top) {
StackNode*t=stack->top;
stack->top=stack->top->next;
if (stack->min&&t <= stack->min) {
StackNode*m=stack->min;
stack->min=stack->min->next;
free(m);
 }
stack->size--;
free(t);
 }
}

intminStackTop(MinStack*stack) {
if (stack&&stack->top) {
returnstack->top->val;
 }
return0;
}

intminStackGetMin(MinStack*stack) {
if (stack&&stack->min) {
returnstack->min->val;
 }
return0;
}

voidminStackDestroy(MinStack*stack) {
if (stack) {
while (stack->size!=0) {
minStackPop(stack);
 }
while (stack->min!=NULL) {
StackNode*m=stack->min;
stack->min=stack->min->next;
free(m);
 }
/**
 *free(stack);
 *stack = NULL;
 */
 }
}

intmain() {
MinStackstack;
minStackCreate(&stack, 10);
inti;
for (i=0; i<5; i++) {
minStackPush(&stack, i);
 }

printf("top: %d\n", minStackTop(&stack));
printf("min: %d\n", minStackGetMin(&stack));

for (i=1; i<5; i++) {
minStackPush(&stack, -i);
 }

printf("top: %d\n", minStackTop(&stack));
printf("min: %d\n", minStackGetMin(&stack));

minStackDestroy(&stack);

return0;
}