分享C++用数组和链表分别实现Stack代码
C++学习有段时间了，感觉还是有很多不足啊，今天自己用数组和链表分别实现Stack，当然STL中的Stack肯定不是这么简单，你不妨看一下，说不定有收获呢，若发现有问题，请指正，毕竟我还是C++新手。数组版
[cpp] view plaincopyprint?//typename可以表示任何类型，而class只能表示类
template<typename T,typename container>
class stack
{
public:
//栈是否为空
bool empty( ) const
{
return index==0;
}
//出栈
void pop( )
{
if(index==0)
{
throw new exception("栈中没有数据");
}
arr[index-1]=0;
--index;
}
//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，
//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组
void push(const T& val)
{
if(index<=capacity-1)
{
arr[index++]=val;
}else
{
capacity<<=1;//capacity对应的二进制数左移一位
int *tmp=new int[capacity];
for(int i=0;i<index;i++)
{
tmp[i]=arr[i];
}
tmp[index++]=val;
delete arr;
arr=tmp;
}
}
//栈中元素个数
int size( ) const
{
return index;
}
stack( )
{
//默认栈中能存放4个元素，当然你会说这样不好，因为如果没有向栈中添加数据，却分配了四个元素的空间，显然不理想。
//为了避免这个问题，可以在push方法的开始判断栈中是否有元素，如果没有元素，就开始分配空间，有元素当然就不用，
//但是有个问题就是每次添加元素都要判断，如果添加元素较多的话，或许你会讨厌总要执行这多余的判断www.
//缓式评估告诉我们，只有到万不得已的情况下才定义变量和分配空间，不然就可能是定义的多余变量和不需要分配的空间
//但当某个变量是必须的，用缓式评估反而影响效率，因为为了实现缓式评估也是要代价的。
initialize(4);
}
//预设栈能容纳cap个元素
stack(int cap)
{
initialize(cap);
}
//explicit防止出现类型转换
explicit stack(const container& cont)
{
initialize(cont.size());
vector <int>::const_iterator iter=cont.begin();
while(iter!=cont.end())
{
push(*iter);
iter++;
}
}
//析构
~stack()
{
delete arr;
}
//输出栈顶元素
T& top( )
{
return arr[index-1];
}
//在C++中，可以重载const和non-const
const T& top( ) const
{
return arr[index-1];
}
private :
int capacity;//容量
int index;//顶部元素的位置
T *arr;//数组
//初始化
//当然，初始化列表比赋值效率高，赋值多调用了一次constructor
void initialize(int cap)
{
capacity=cap;
arr=new T[capacity];
index=0;
}
};
指针版
[csharp] view plaincopyprint?#include <vector>
using namespace std;
template<typename T,typename container>
class stack
{
public:
bool empty( ) const
{
return len==0;
}
//出栈
void pop( )
{
if(len==0)
{
throw new exception("栈中没有数据");
}
if(head->next==cur)//删除第一个元素
{
delete cur;
head->next=NULL;
}else{ //删除最后一个元素
node *tmp=head->next;
//将指针移到最后第二个元素
for(int i=2;i<len;i++)//对比把for循环写成for(int i=0;i<len-2;i++)
{
tmp=tmp->next;
}
delete tmp->next; //析构最后一个元素
cur=tmp;//将指针指到现在的最后一个元素
}
--len;//元素个数减一
}
//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，
//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组
void push(const T& val)
{
node *tmp=new node(val);//新建节点
cur->next=tmp;//将当前节点的下一个节点指向新增节点
cur=tmp;//当前节点指向新节点
++len;//节点个数加1
}
int size( ) const
{
return len;
}
stack( )
{
initialize();
}
//析构
~stack()
{
delete head;
}
explicit stack(const container& cont)
{
initialize();
//cont.begin()是常量类型，所以这里只能用vector <int>::const_iterator而不能用vector <int>::iterator
vector <int>::const_iterator iter=cont.begin();
while(iter!=cont.end())
{
push(*iter);
iter++;
}
}
T& top( )
{
return cur->val;
}
const T& top( ) const
{
return cur->val;
}
protected :
typedef struct node1
{
node1 *next;
T val;
node1(T v):val(v),next(NULL){}
}node;
private :
int len;//元素个数
node *head;//表头节点
node *cur;//当前节点
void initialize()
{
head=new node(-1);
cur=head;
len=0;
}
};
Int版
[cpp] view plaincopyprint?class stack
{
public:
bool empty( ) const
{
return index==0;
}
//出栈
void pop( )
{
if(index==0)
{
throw new exception("栈中没有数据");
}
arr[index-1]=0;
--index;
}
//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，
//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组
void push(const int& val)
{
if(index<=capacity-1)
{
arr[index++]=val;
}else
{
capacity<<=1;
int *tmp=new int[capacity];
for(int i=0;i<index;i++)
{
tmp[i]=arr[i];
}
tmp[index++]=val;
delete arr;
arr=tmp;
}
}
int size( ) const
{
return index;
}
stack( )
{
initialize(4);
}
stack(int cap)
{
initialize(cap);
}
//析构
~stack()
{
delete arr;
}
int& top( )
{
return arr[index-1];
}
const int& top( ) const
{
return arr[index-1];
}
private :
int capacity;//容量
int index;//顶部元素的位置
int *arr;//数组 www.
//初始化
//当然，初始化列表比赋值效率高，赋值多调用了一次constructor
void initialize(int cap)
{
capacity=cap;
arr=new int[capacity];
index=0;
}
};
