C++用数组和链表分别实现Stack

C++用数组和链表分别实现Stack

C++学习有段时间了，感觉还是有很多不足啊，今天自己用数组和链表分别实现Stack，当然STL中的Stack肯定不是这么简单，你不妨看一下，说不定有收获呢，若发现有问题，请指正，毕竟对于C++我还是新手。

数组版//typename可以表示任何类型，而class只能表示类

template<typename T,typename container>

classstack

{

public:

//栈是否为空

boolempty( )const

{

returnindex==0;

}



//出栈

voidpop( )

{

if(empty())

{

thrownewexception("栈中没有数据");

}

arr[index-1]=0;

--index;

}



//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，

//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组

voidpush(constT&val)

{

if(index<=capacity-1)

{

arr[index++]=val;

}else

{

capacity<<=1;//capacity对应的二进制数左移一位

inttmp=newint[capacity];

for(inti=0;i<index;i++)

{

tmp[i]=arr[i];

}

tmp[index++]=val;

delete arr;

arr=tmp;

}

}



//栈中元素个数

intsize( )const

{

returnindex;

}



stack( )

{

//默认栈中能存放4个元素，当然你会说这样不好，因为如果没有向栈中添加数据，却分配了四个元素的空间，显然不理想。

//为了避免这个问题，可以在push方法的开始判断栈中是否有元素，如果没有元素，就开始分配空间，有元素当然就不用，

//但是有个问题就是每次添加元素都要判断，如果添加元素较多的话，或许你会讨厌总要执行这多余的判断

//缓式评估告诉我们，只有到万不得已的情况下才定义变量和分配空间，不然就可能是定义的多余变量和不需要分配的空间

//但当某个变量是必须的，用缓式评估反而影响效率，因为为了实现缓式评估也是要代价的。

initialize(4);

}



//预设栈能容纳cap个元素

stack(intcap)

{

initialize(cap);

}



//explicit防止出现类型转换

explicitstack(constcontainer&cont)

{

initialize(cont.size());

vector<int>::const_iterator iter=cont.begin();

while(iter!=cont.end())

{

push(iter++);

}

}



//析构

~stack()

{

delete arr;

}



//输出栈顶元素

T&top( )

{

returnarr[index-1];

}



//在C++中，可以重载const和non-const

constT&top( )const

{

returnarr[index-1];

}



private:

intcapacity;//容量

intindex;//顶部元素的位置

Tarr;//数组



//初始化

//当然，初始化列表比赋值效率高，赋值多调用了一次constructor

voidinitialize(intcap)

{

capacity=cap;

arr=newT[capacity];

index=0;

}

};链表版#include<vector>

usingnamespacestd;

template<typename T,typename container>

classstack

{

public:

boolempty( )const

{

returnlen==0;

}



//出栈

voidpop( )

{

if(empty( ))

{

thrownewexception("栈中没有数据");

}



if(head->next==cur)//删除第一个元素

{

delete cur;

head->next=NULL;

}else{//删除最后一个元素

nodetmp=head->next;

//将指针移到最后第二个元素

for(inti=2;i<len;i++)//对比把for循环写成for(int i=0;i\\
\
\\{\
\
tmp\\=\\tmp\\->next;

}

delete tmp->next;//析构最后一个元素

cur=tmp;//将指针指到现在的最后一个元素

}

--len;//元素个数减一

}



//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，

//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组

voidpush(constT&val)

{

nodetmp=newnode(val);//新建节点

cur->next=tmp;//将当前节点的下一个节点指向新增节点

cur=tmp;//当前节点指向新节点

++len;//节点个数加1

}



intsize( )const

{

returnlen;

}



stack( )

{

initialize();

}



//析构

~stack()

{

delete head;

}



explicitstack(constcontainer&cont)

{

initialize();

//cont.begin()是常量类型，所以这里只能用vector ::const_iterator而不能用vector ::iterator

vector<int>::const_iterator iter=cont.begin();

while(iter!=cont.end())

{

push(iter);

iter++;

}

}



T&top( )

{

returncur->val;

}



constT&top( )const

{

returncur->val;

}



protected:

typedefstructnode1

{

node1next;

T val;

node1(T v):val(v),next(NULL){}

}node;



private:

intlen;//元素个数

nodehead;//表头节点

node*cur;//当前节点

voidinitialize()

{

head=newnode(-1);

cur=head;

len=0;

}

};

Int版classstack

{

public:

boolempty( )const

{

returnindex==0;

}



//出栈

voidpop( )

{

if(empty())

{

thrownewexception("栈中没有数据");

}

arr[index-1]=0;

--index;

}



//出栈，如果默认数组未满继续添加数据，如果已满，重新分配一个两倍的数组，

//把默认数组中的数据拷贝过来，释放默认数组,将指针指向新数组

voidpush(constint&val)

{

if(index<=capacity-1)

{

arr[index++]=val;

}else

{

capacity<<=1;

inttmp=newint[capacity];

for(inti=0;i<index;i++)

{

tmp[i]=arr[i];

}

tmp[index++]=val;

delete arr;

arr=tmp;

}

}



intsize( )const

{

returnindex;

}



stack( )

{

initialize(4);

}



stack(intcap)

{

initialize(cap);

}



//析构

~stack()

{

delete arr;

}



int&top( )

{

returnarr[index-1];

}



constint&top( )const

{

returnarr[index-1];

}



private:

intcapacity;//容量

intindex;//顶部元素的位置

intarr;//数组



//初始化

//当然，初始化列表比赋值效率高，赋值多调用了一次constructor

voidinitialize(intcap)

{

capacity=cap;

arr=newint[capacity];

index=0;

}

};
作者：陈太汉
原文链接: https://www.cnblogs.com/hlxs/archive/2011/07/11/2103309.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍