实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)
创新互联建站坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站设计、网站建设、外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的港口网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
具体实现如下：
#include
#include
#include
#include
using namespace std;
template
class Stack
{
public:
void Push(const T& x);
void Pop();
T& Min();
void PrintS();
private:
stack Sk;//存放栈中所有元素的
stack MinSk;//存放栈中最小元素的
};
template
void Stack::Push(const T& x)
{
Sk.push(x);
//当MinSk为空时，先存放一个元素；当比较入栈元素小于栈顶元素时，入栈
if (MinSk.empty() || x < MinSk.top())
{
MinSk.push(x);
}
}
template
void Stack::Pop()
{
if (Sk.empty())
{
cout << "stack is empty!" << endl;
return;
}
//如果出栈元素等于MinSk中栈顶元素，则MinSk需pop()该元素，使MinSk栈顶始终存放Sk栈中最小元素
if (Sk.top() == MinSk.top())
{
MinSk.pop();
}
Sk.pop();
}
template
T& Stack::Min()
{
assert(!MinSk.empty());
return MinSk.top();
}
template
void Stack::PrintS()
{
if (Sk.empty())
{
cout << "stack is empty!" << endl;
return;
}
stack tmp = Sk;
stack mintmp = MinSk;
cout << "stack: ";
while (!tmp.empty())
{
cout << tmp.top() << " ";
tmp.pop();
}
cout << "\nminstack: ";
while (!mintmp.empty())
{
cout << mintmp.top() << " ";
mintmp.pop();
}
cout << endl;
}
//测试用例
void Test4()
{
//Stack s1;
//s1.Push(9);
//s1.Push(5);
//s1.Push(7);
//s1.Push(3);
//s1.Push(8);
////s1.Pop();
////s1.Pop();
////s1.Pop();
////s1.Pop();
////s1.Pop();
////s1.Pop();
Stack s1;
s1.Push("sssss");
s1.Push("syikl");
s1.Push("yyyyy");
s1.Push("fffff");
s1.Push("lllll");
s1.PrintS();
cout << s1.Min() << endl;
}
【干货小知识】自主实现一个栈，具体实现如下：
template
class Stack
{
public:
Stack()
:_arr(NULL)
, _size(0)
, _capacity(0)
{}
Stack(const Stack& s)
:_arr(new T[s._size])
, _size(s._size)
, _capacity(s._size)
{
for (size_t i = 0; i < _size; i++)
{
_arr[i] = s._arr[i];
}
}
Stack& operator=(const Stack& s)
{
if (this != &s)
{
T* tmp = new T[s._size];
delete[] _arr;
for (size_t i = 0; i < s._size; i++)
{
tmp[i] = s._arr[i];
}
_arr = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
~Stack()
{
if (_arr)
{
delete[] _arr;
}
}
public:
void _CheckCapacity(size_t size)
{
if (size > _capacity)
{
_capacity += _capacity * 2 + 3;
}
T* tmp = new T[_capacity];
if (_arr)
{
for (size_t i = 0; i < _size; i++)
{
tmp[i] = _arr[i];
}
}
delete[] _arr;
_arr = tmp;
}
void Push(const T& x)
{
_CheckCapacity(_size + 1);
_arr[_size++] = x;
}
void Pop()
{
assert(_size > 0);
--_size;
}
bool Empty()
{
return _size == 0;
}
size_t Size()
{
return _size;
}
T& Top()
{
return _arr[_size - 1];
}
void PrintStack()
{
if (_size == 0)
{
cout << "Stack is empty!";
}
else
{
for (size_t i = 0; i < _size; i++)
{
cout << _arr[i] << " ";
}
cout << endl;
}
}
private:
T* _arr;
size_t _size;
size_t _capacity;
};
文章标题：实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)
文章源于：
http://bjjierui.cn/article/jeeecj.html
