算法面试题五

试用多态实现线性表（队列，串，堆栈），要求具备线性表的基本操作（pop，push，测长等）

这里实现其共性模板，代码如下：

#include <iostream>
#include <string.h>
#include <climits>
#include <new>
#include <stdio.h>
#include <io.h>
#include <fcntl.h>
#include <string.h>
#include <iomanip>

template<class T>
class tcontainer{
public:
virtual void push(T &a)=0;
virtual void pop(void)=0;
virtual int size(void)=0;
};

template<class T>
class tvector : public tcontainer<T>{
public:
static const int step=100;
tvector(){
_size = 0;
_cap = step;
_buf = 0;
re_capacity(_cap);
};
~tvector(){
if(_buf)
free(_buf);
};
virtual void re_capacity(int s){
if(_buf)
_buf=(T *)realloc(_buf,s*sizeof(T));
else{
_buf=(T*)malloc(sizeof(T)*s);
}
};
virtual void push(T &a){
_size++;
if(_size>_cap)
re_capacity(_cap+=step);
_buf[_size-1] = a;
}
virtual void pop(void){
if(_size)
_size--;
}
virtual int size(void){
return _size;
}
const T &operator[](int index){
if(index>=0&&index<_size)
return *(_buf+index);
} 
private:
int _cap;
int _size;
T* _buf;
};


int main(int argc, char *argv[])
{ 
tvector<int> v;
for(int i=0;i<300;++i)
v.push(i);
    for(int i=1;i<301;++i)
(i%15==0)?(cout<<v[i-1]<<endl):(cout<<setw(3)<<v[i-1]<<" ");

getchar();
return 0;
}

测试结果：