微软面试100题之第2题

设计包含 min函数的栈

定义栈的数据结构，要求添加一个 min函数，能够得到栈的最小元素。

要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct StackElement{
    int data;
    int min;
}StackElement;


typedef struct Stack{
    StackElement data[MAXSIZE];
    int top;
}Stack;

void init(Stack &stack){
    stack.top = 0;
}

void push(Stack &stack,int value){
    if(stack.top < MAXSIZE){
        stack.data[stack.top].data = value;
        stack.data[stack.top].min = stack.top==0?value:stack.data[stack.top-1].min;
        if(stack.data[stack.top].min>value)
            stack.data[stack.top].min = value;
        stack.top++;
    }
    else{
        printf("error:the stack is full,value %d isn't pushed.\n",value);
        exit(EXIT_FAILURE);
    }
}

int pop(Stack &stack){
    if(stack.top > 0){
        return stack.data[--stack.top].data;
    }
    else{
        printf("error:the stack is empty.\n");
        exit(EXIT_FAILURE);
    }
}

int min(Stack stack){
    if(stack.top==0){
        printf("error:the stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return stack.data[stack.top-1].min;
}

main(){
    int i = 0;
    Stack stack;
    init(stack);
    for(i=256;i>200;i--)
        push(stack,i);
    printf("the min value is %d",min(stack));
}