微软等数据结构与算法面试100题 第二题

第二题

题目： 要求设计一个栈，栈包含min函数的功能，即能够在O(1)的时间内做min， pop， push运算。

分析：
因为传统的栈只有push和pop功能，push和pop功能都是在O（1）的时间内做操作，题目要求具有min函数的功能，也就是在pop操作和push操作以后可以
在O（1）的时间内给出最小值的功能。因为如果是直接增加min函数，那么每次计算最小值的时候都是O(N)的时间，为了要达到O（1）的时间，因此需要一个
数组来存储这一动态变化过程，min_array中min_array[k]存储前K个数字里面最小值。

代码：
[cpp]
#include
using namespace std;


template
class Stack{

private:

int size;
T * data;
int top;
T * min_data;
T min_value;

public:

Stack(int size = 100);
~Stack();

T pop();
//为什么要去地址呢

void push(const T item);
void print(){cout<

};

template
Stack::Stack(int size){

data = new T [size];
min_data = new T [size];
this->top = -1;

}

template
Stack::~Stack()
{

delete []data;
delete []min_data;
}


template
void Stack::push(const T item)
{
if(top==size-1){
cout<<"堆栈溢出"< //return;
}
top ++;
data[top]=item;

if(top==0)
{
min_data[top] = item;
min_value = item;
}
else
{
if(item < min_data[top-1])
{
min_data[top] = item;
min_value = item;
}
else
{
min_data[top] = min_data[top-1];
this->min_value = min_data[top-1];
}
}
}

template
T Stack::pop()
{
if(top==-1)
{
cout<<"堆栈空"< return -1;
}

T DATA_POP = data[top];

min_value = min_data[top-1];

top = top -1;



return DATA_POP;

}


int main(){

int stack_size = 100;
Stack a_value(stack_size);

// test
a_value.push(10);
a_value.print();

a_value.push(2);
a_value.print();

a_value.push(3);
a_value.print();

a_value.push(1);
a_value.print();
a_value.push(5);
a_value.print();

cout<<"sc"< a_value.pop();
a_value.print();

a_value.pop();
a_value.print();


return 0;
}