/*下面stack是原始的定义:
这个原始的Stack的定义有两个缺点：
第一：长度是固定的，并且还浪费了一个槽，用做指向顶端的指针。
第二：只支持int类型也就是说它是个int Stack类
就像这种类最难理解的地方就是边界的部分！
抢答：
#include <vector>
#include <iostream>
int main()
{
vector<int> ivec(32);
ivec[32] = 64;
cout <<” size of ivec “ << ivec.size()<<endl;
cout <<” ivec[32] “ << ivec[32]<<endl;
}
上面程序的执行结果是什么？
只要理解了上面的程序，下面这个就是小菜一碟了，不信呀，自己试试。
ivec(32)这东西，能装下32个整数，但第32个整数它装不下。什么，你问我为什么，因为数数的时候是从0开始数的。
其实，用vector来实现stack有些暴殄天物，因为vector是能够动态增长的，原始的这个iStack类不如用数组来实现更好，而且更容易理解。
#include <vector>
#include <iostream> //这是我增加的
using namespace std; //这是我增加的
class iStack {
public:
iStack( int capacity )
: _stack( capacity ), _top( 0 ) {};
bool pop( int &value );
bool push( int value );
bool full();
bool empty();
_top
void display();
86
int size();
42
private:
39
int _top; //跟踪下一个可用的槽
vector< int> _stack; //这里删除了allocator
};
inline int iStack::size() { return _top; };
inline bool iStack::empty() { return _top ? false : true; }
inline bool iStack::full() { return _top < _stack.size()-1 ? false : true; };
bool iStack::pop( int &top_value )
{
if ( empty() )
return false;
top_value = _stack[ --_top ];
cout << "iStack::pop(): " << top_value << endl;
return true;
}
bool iStack::push( int value ) {
cout << "iStack::push( " << value << " )\n";
if ( full() )
return false;
_stack[ _top++ ] = value;
return true;
};
void iStack::display()
{
cout << "( " << size() << " )( bot: ";
for ( int ix = 0; ix < _top; ++ix )
cout << _stack[ ix ] << " ";
cout << " :top )\n";
};
// #include <iostream>
//#include <iostream.h> 这是我删除的
int main()
{
iStack stack( 32 );
stack.display();
for ( int ix = 1; ix < 51; ++ix )
{
if ( ix%2 == 0 )
stack.push( ix );
if ( ix%5 == 0 )
stack.display();
if ( ix%10 == 0) {
int dummy;
stack.pop( dummy ); stack.pop( dummy );
stack.display();
}
}
}
//正因为用了以上那些缺点，所以使得Stack演进：请看 ”C++ Primer “ p272，
p272的程序解决了第一个缺点。
下面使用模板解决第二个缺点：
#include <vector>
#include <iostream>
using namespace std;
template <class elemType>
class Stack{
public:
Stack( ){ {}
Stack(int capacity = 0)；
bool pop(elemType &value);
bool push(elemType value);
bool peek(elemType &value);
bool full();
bool empty();
void display();
int size();
private:
vector<elemType>_stack;
};
template<class elemType>
inline Stack::Stack(int capacity)
{
if(capacity)
_stack.reserve( capacity );
}
template<class elemType>
inline bool Stack<elemType>::empty(){ return _stack.empty(); }
template<typename elemType>
inline int Stack<elemType>::size()
{
return _stack.size();
}
template<class elemType>
inline bool Stack<elemType>::full()
{
return _stack.max_size() == _stack.size();
}
template <class elemType>
bool Stack<elemType>::pop(elemType &top_value)
{
if(empty())
return false;
top_value = _stack[ size()-1 ];
_stack.pop_back();
cout << "Stack::pop():"<<top_value<<endl;
return true;
}
template<class elemType>
bool Stack<elemType>::push(elemType value)
{
if(full())
return false;
cout<<"Stack::push("<<value<<")\n";
_stack.push_back(value);
return true;
}
template<class elemType>
void Stack<elemType>::display()
{
cout<<"("<<size()<<")(bot:";
for(int ix = 0; ix < size(); ++ix)
cout<<_stack[ix]<<" ";
cout<<":top)\n";
}
template<class elemType>
bool Stack<elemType>::peek(elemType &stop_value)
{
if(empty())
return false;
top_value = _stack[ size()-1 ];
cout << "Stack::peek(): "<<top_value<<endl;
return true;
}
//应该注意的是即使没用用到elemType的类的成员函数也要加上template<class elemType>