定义栈的数据结构,要求添加一个 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;
}
