第二題
題目： 要求設計一個棧，棧包含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<iostream>
using namespace std;
template <class T>
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<<min_value<<endl;}
};
template<class T>
Stack<T>::Stack(int size){
data = new T [size];
min_data = new T [size];
this->top = -1;
}
template<class T>
Stack<T>::~Stack()
{
delete []data;
delete []min_data;
}
template<class T>
void Stack<T>::push(const T item)
{
if(top==size-1){
cout<<"堆棧溢出"<<endl;
//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<class T>
T Stack<T>::pop()
{
if(top==-1)
{
cout<<"堆棧空"<<endl;
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<int> 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"<<endl;
a_value.pop();
a_value.print();
a_value.pop();
a_value.print();
return 0;
}
