【微软面试一百题：2】设计包含 min 函数的栈

定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

hint: 栈元素携带min的信息

#include<iostream>
#include <stdlib.h>
using namespace std;

struct MinStackElement {
    int data;
    int min;
};

struct MinStack{
    int size;
    int top;
    MinStackElement * data;
};

MinStack minStackInit(int maxSize){
    MinStack stack;
    stack.size = maxSize;
    stack.data = (MinStackElement *)
    malloc(sizeof(MinStackElement)*maxSize);
    stack.top = 0;
    return  stack;
}

void MinStackFree(MinStack &stack){
    free(stack.data);
}

void push(MinStack &stack,int d){
    if (stack.top==stack.size) {
       // error("out of stack");
    }
    MinStackElement* p = stack.data+stack.top;
    p->data = d;
    p->min = (stack.top==0 ?d:stack.data[stack.top-1].min);
    if (d<p->min) {
        p->min = d;
    }
    stack.top++;
}

int pop(MinStack stack){
    if (stack.top ==0) {
        //error("stack is empty");
    }
    return stack.data[--stack.top].data;
}

int min(MinStack stack){
    if (stack.top ==0) {
        //error("stack is empty");
    }
    return stack.data[--stack.top].min;
}

int main(){
    MinStack stack = minStackInit(6);
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    push(stack, 4);
    push(stack, 5);
    push(stack, 6);
    cout<<pop(stack)<<endl;
    cout<<min(stack)<<endl;
    MinStackFree(stack);
    return  0;
}