设计包含 min函数的栈()
定义栈的数据结构,要求添加一个 minminmin函数,能够得到栈的最小元素。
要求函数 min、push以及 pop 的时间复杂度都是 O(1)。
#include <iostream>
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-1])
{
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<<stk.min();
return 0;
}
- #include <iostream>
- 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-1])
- {
- 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<<stk.min();
- return 0;
- }
#include <iostream>
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-1])
{
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<<stk.min();
return 0;
}