設計包含 min函數的棧()
定義棧的數據結構，要求添加一個 minminmin函數，能夠得到棧的最小元素。
要求函數 min、push以及 pop 的時間復雜度都是 O(1)。
#include?
using?namespace?std;
/*by?hk?2015-7-1*/
#define?MAX?((~(unsigned?int?)0)-1)/2
class?stack
{
public:
int?stack_data[100];/*數據元素*/
int?stack_min[100];/*每次插入值?對于當前最小值*/
int?iter;
int?iter_min;
stack()
{
iter=0;
iter_min=1;
stack_min[1]=MAX;
}
void?pop()
{
if(iter>0)
{
--iter;
--iter_min;
}
}
void?push(int?x)
{
if(iter<99)
{
stack_data[iter++]=x;
if(x
{
stack_min[iter_min++]=x;
stack_min[iter_min]=MAX;
}
else
{
stack_min[iter_min]=stack_min[iter_min-1];
++iter_min;
}
}
}
int?min()
{
return?stack_min[iter_min-1];
}
};
int?main(int?argc,?char?*argv[])
{
stack?stk;
stk.push(7);
stk.push(3);
stk.push(2);
stk.push(8);
stk.push(1);
stk.pop();
cout<
return?0;
}
)
