C++用數(shù)組和鏈表分別實(shí)現(xiàn)Stack

C++用數(shù)組和鏈表分別實(shí)現(xiàn)Stack

　　C++學(xué)習(xí)有段時(shí)間了，感覺(jué)還是有很多不足啊，今天自己用數(shù)組和鏈表分別實(shí)現(xiàn)Stack，當(dāng)然STL中的Stack肯定不是這么簡(jiǎn)單，你不妨看一下，說(shuō)不定有收獲呢，若發(fā)現(xiàn)有問(wèn)題，請(qǐng)指正，畢竟對(duì)于C++我還是新手。

數(shù)組版

//typename可以表示任何類型，而class只能表示類
template<typename T,typename container>
class stack
{
public:
//棧是否為空
bool empty( ) const
{
return index==0;
}

//出棧
void pop( )
{
if(empty())
{
thrownew exception("棧中沒(méi)有數(shù)據(jù)");
}
arr[index-1]=0;
--index;
}

//出棧，如果默認(rèn)數(shù)組未滿繼續(xù)添加數(shù)據(jù)，如果已滿，重新分配一個(gè)兩倍的數(shù)組，
//把默認(rèn)數(shù)組中的數(shù)據(jù)拷貝過(guò)來(lái)，釋放默認(rèn)數(shù)組,將指針指向新數(shù)組
void push(const T& val)
{
if(index<=capacity-1)
{
arr[index++]=val;
}else
{
capacity<<=1;//capacity對(duì)應(yīng)的二進(jìn)制數(shù)左移一位
int*tmp=newint[capacity];
for(int i=0;i<index;i++)
{
tmp[i]=arr[i];
}
tmp[index++]=val;
delete arr;
arr=tmp;
}
}

//棧中元素個(gè)數(shù)
int size( ) const
{
return index;
}

stack( )
{
//默認(rèn)棧中能存放4個(gè)元素，當(dāng)然你會(huì)說(shuō)這樣不好，因?yàn)槿绻麤](méi)有向棧中添加數(shù)據(jù)，卻分配了四個(gè)元素的空間，顯然不理想。
//為了避免這個(gè)問(wèn)題，可以在push方法的開始判斷棧中是否有元素，如果沒(méi)有元素，就開始分配空間，有元素當(dāng)然就不用，
//但是有個(gè)問(wèn)題就是每次添加元素都要判斷，如果添加元素較多的話，或許你會(huì)討厭總要執(zhí)行這多余的判斷
//緩式評(píng)估告訴我們，只有到萬(wàn)不得已的情況下才定義變量和分配空間，不然就可能是定義的多余變量和不需要分配的空間
//但當(dāng)某個(gè)變量是必須的，用緩式評(píng)估反而影響效率，因?yàn)闉榱藢?shí)現(xiàn)緩式評(píng)估也是要代價(jià)的。
initialize(4);
}

//預(yù)設(shè)棧能容納cap個(gè)元素
stack(int cap)
{
initialize(cap);
}

//explicit防止出現(xiàn)類型轉(zhuǎn)換
explicit stack(const container& cont)
{
initialize(cont.size());
vector <int>::const_iterator iter=cont.begin();
while(iter!=cont.end())
{
push(*iter++);
}
}

//析構(gòu)
~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;//數(shù)組

//初始化
//當(dāng)然，初始化列表比賦值效率高，賦值多調(diào)用了一次constructor
void initialize(int cap)
{
capacity=cap;
arr=new T[capacity];
index=0;
}
};

鏈表版

#include <vector>
usingnamespace std;
template<typename T,typename container>
class stack
{
public:
bool empty( ) const
{
return len==0;
}

//出棧
void pop( )
{
if(empty( ))
{
thrownew exception("棧中沒(méi)有數(shù)據(jù)");
}

if(head->next==cur)//刪除第一個(gè)元素
{
delete cur;
head->next=NULL;
}else{ //刪除最后一個(gè)元素
node *tmp=head->next;
//將指針移到最后第二個(gè)元素
for(int i=2;i<len;i++)//對(duì)比把for循環(huán)寫成for(int i=0;i<len-2;i++)
{
tmp=tmp->next;
}
delete tmp->next; //析構(gòu)最后一個(gè)元素
cur=tmp;//將指針指到現(xiàn)在的最后一個(gè)元素
}
--len;//元素個(gè)數(shù)減一
}

//出棧，如果默認(rèn)數(shù)組未滿繼續(xù)添加數(shù)據(jù)，如果已滿，重新分配一個(gè)兩倍的數(shù)組，
//把默認(rèn)數(shù)組中的數(shù)據(jù)拷貝過(guò)來(lái)，釋放默認(rèn)數(shù)組,將指針指向新數(shù)組
void push(const T& val)
{
node *tmp=new node(val);//新建節(jié)點(diǎn)
cur->next=tmp;//將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新增節(jié)點(diǎn)
cur=tmp;//當(dāng)前節(jié)點(diǎn)指向新節(jié)點(diǎn)
++len;//節(jié)點(diǎn)個(gè)數(shù)加1
}

int size( ) const
{
return len;
}

stack( )
{
initialize();
}

//析構(gòu)
~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;//元素個(gè)數(shù)
node *head;//表頭節(jié)點(diǎn)
node *cur;//當(dāng)前節(jié)點(diǎn)
void initialize()
{
head=new node(-1);
cur=head;
len=0;
}
};

Int版

class stack
{
public:
bool empty( ) const
{
return index==0;
}

//出棧
void pop( )
{
if(empty())
{
thrownew exception("棧中沒(méi)有數(shù)據(jù)");
}
arr[index-1]=0;
--index;
}

//出棧，如果默認(rèn)數(shù)組未滿繼續(xù)添加數(shù)據(jù)，如果已滿，重新分配一個(gè)兩倍的數(shù)組，
//把默認(rèn)數(shù)組中的數(shù)據(jù)拷貝過(guò)來(lái)，釋放默認(rèn)數(shù)組,將指針指向新數(shù)組
void push(constint& val)
{
if(index<=capacity-1)
{
arr[index++]=val;
}else
{
capacity<<=1;
int*tmp=newint[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);
}

//析構(gòu)
~stack()
{
delete arr;
}

int& top( )
{
return arr[index-1];
}

constint& top( ) const
{
return arr[index-1];
}

private :
int capacity;//容量
int index;//頂部元素的位置
int*arr;//數(shù)組

//初始化
//當(dāng)然，初始化列表比賦值效率高，賦值多調(diào)用了一次constructor
void initialize(int cap)
{
capacity=cap;
arr=newint[capacity];
index=0;
}
};

作者：陳太漢