C++棧的數(shù)組實(shí)現(xiàn)代碼
棧的抽象數(shù)據(jù)結(jié)構(gòu)。棧的成員函數(shù)需要包括這幾個(gè)基本的函數(shù)：initializeStack(),isEmptyStack(),isFullStack,push(),pop(),top()
其功能如下：
- initializeStack():初始化棧
- isEmptyStack():判斷棧是否為空
- isFullStack():判斷棧是否已滿(mǎn)
- push():將一個(gè)元素壓入棧中
- pop():刪除棧頂元素
- top():獲得棧頂元素
? C++中用抽象類(lèi)作為基類(lèi)實(shí)現(xiàn)ADT如下：
template<class Type>
class stackADT
{
virtual void initializeStack()=0;//virtual和=0表明都是純虛函數(shù)，抽象類(lèi)中只能聲明純虛函數(shù)，不能定義
virtual bool isEmptyStack() const=0;//const放在函數(shù)后面，表明該函數(shù)是常成員函數(shù)，在函數(shù)執(zhí)行過(guò)程中不能改變函數(shù)內(nèi)部變量的值
virtual bool isFullStack() const=0;
virtual void push(const Type&)=0;//引用常量，該函數(shù)不會(huì)自動(dòng)對(duì)輸入進(jìn)行賦值，同時(shí)在函數(shù)內(nèi)的操作也不能改變輸入的值
virtual void pop()=0;
virtual Type top() const=0;//這里也采用常成員函數(shù)，因?yàn)楹瘮?shù)不會(huì)對(duì)變量進(jìn)行修改，只是返回變量
};
? 補(bǔ)充說(shuō)明：
- 抽象類(lèi)：一個(gè)類(lèi)中只要有一個(gè)純虛函數(shù)，那么該類(lèi)就是抽象類(lèi)，抽象類(lèi)通常作為基類(lèi)，純虛函數(shù)在抽象類(lèi)中只能聲明不能定義。
- 常成員函數(shù)：什么時(shí)候才使用常成員函數(shù)？一般在如果該函數(shù)在執(zhí)行過(guò)程中不會(huì)有改變變量值的操作，就會(huì)把該函數(shù)定義為常成員函數(shù)。
- 常引用：常引用一般用于函數(shù)輸入，或者函數(shù)返回值。如函數(shù)輸入是常引用類(lèi)型，那么說(shuō)明該函數(shù)只會(huì)用到引用的值，而不會(huì)改變引用變量的值，同時(shí)可能引用變量的類(lèi)型可能很大比較占內(nèi)存，所以用引用可以避免輸入?yún)?shù)的復(fù)制，從而節(jié)約了空間；若函數(shù)返回值為常引用類(lèi)型，那么有兩個(gè)原因，首先const表示返回值不能被修改（注意和常成員函數(shù)做區(qū)分），引用則表示函數(shù)返回時(shí)不會(huì)對(duì)返回變量進(jìn)行拷貝，從而不會(huì)觸發(fā)拷貝函數(shù)，因此經(jīng)常被用于運(yùn)算符重載，但是要注意返回值不能是函數(shù)局部變量，因?yàn)榫植孔兞吭诤瘮?shù)結(jié)束后會(huì)被釋放，從而引用了不合法的內(nèi)存，會(huì)報(bào)錯(cuò)，像如果是運(yùn)算符重載返回的基本是this指向的對(duì)象，這對(duì)于函數(shù)來(lái)說(shuō)則是全局的，所以是沒(méi)問(wèn)題的，一般如果返回值是對(duì)象，且要避免拷貝，那么就把返回值類(lèi)型設(shè)置為常引用?？傊米鳛檩斎?yún)?shù)或者返回值時(shí)就是為了避免產(chǎn)生副本，而const則是為了保證變量不被修改。
- 棧的動(dòng)態(tài)數(shù)組實(shí)現(xiàn)
? 直接繼承抽象類(lèi)，不管是動(dòng)態(tài)數(shù)組實(shí)現(xiàn)還是鏈表實(shí)現(xiàn)，抽象類(lèi)的那幾個(gè)成員函數(shù)都是需要的，但是函數(shù)實(shí)現(xiàn)的內(nèi)容不一樣
? 這就體現(xiàn)了多態(tài)了。
? 下面是派生棧類(lèi)的定義：
template <class Type>
class stackType:public stackADT<Type> //一定要記住每次用到模板類(lèi)時(shí)不要忘記后面的<Type>
{
public:
stackType(int stackSize=100);//注意這里用到了參數(shù)缺省構(gòu)造函數(shù)中的參數(shù)缺省必須在聲明函數(shù)時(shí)給出默認(rèn)值而不能在定義函數(shù)時(shí)給出默認(rèn)值；stackType作為函數(shù)名，因此后面不要加<Type>
stackType(const stackType<Type>&); //拷貝構(gòu)造函數(shù)
~stackType();
const stackType<Type>& operator=(const stackType<Type>&);//重載賦值運(yùn)算符
void initializeStack();
bool isEmptyStack()const;
bool isFullStack()const;
void push(const Type&);
void pop();
Type top()const;
private:
Type* list;//指向棧的首地址
int maxStackSize;//棧的最大容量
int stackTop;//棧頂元素的位置(從1開(kāi)始)
void copyStack(const stackType<Type>&);//執(zhí)行深拷貝過(guò)程
};//注意不要忘記分號(hào)
? 成員函數(shù)的實(shí)現(xiàn)如下：
? initializeStack():
template<class Type>//在類(lèi)外定義函數(shù)必須使用template，并且每定義一個(gè)函數(shù)就要寫(xiě)一次
void stackType<Type>::initializeStack() //命名空間也不要忘記::,因?yàn)槊臻g的名字是模板類(lèi)，所以后面要有<Type>
{
stackTop=0;//不需要把元素全部置零，只需要把棧頂元素的索引變成0即可
}
? isEmptyStack():
template<class Type>
bool stackType<Type>::isEmptyStack()const
{
return !stackTop;//可以認(rèn)為stackTop表示棧中目前元素的個(gè)數(shù)，為0則表示空棧
}
? isFullStack():
template<class Type>
bool stackType<Type>::isFullStack()const
{
return stackTop==maxStackSize;
}
? push():
template<class Type>
void stackType<Type>::pop()
{
if(!isEmptyStack())
stackTop--;
else
cout<<"The stack is empty,cannot add to an item"<<endl;
}
? pop():
template<class Type>
void stackType<Type>::pop()
{
if(!isEmptyStack())
stackTop--;
else
cout<<"The stack is empty,cannot add to an item"<<endl;
}
? top():
template<class Type>
Type stackType<Type>::top()const
{
assert(!isEmptyStack());//如果棧為空那么必須終止程序，reuturn 返回的會(huì)是亂碼，push和pop不需要這個(gè)操作是因?yàn)樗麄儧](méi)有返回值，所以如果不滿(mǎn)足執(zhí)行的條件只需要在終端上顯示出現(xiàn)異常就行。
return list[stackTop-1];
}
?copyStack():
template<class Type>
void stackType<Type>::copyStack(const stackType<Type>& otherStack)
{
delete [] list; //釋放當(dāng)前棧的內(nèi)存,注意如果delete的是一個(gè)空指針，那么delete不會(huì)執(zhí)行，因此就不需要判斷是否為空指針
stackTop=otherStack.stackTop;
maxStackSize=otherStack.maxStackSize;
list=new Type[maxStackSize]; //
for(int i=0;i<stackTop;i++)
list[i]=otherStack.list[i];
}
?stackType():構(gòu)造函數(shù)
template<class Type>
stackType<Type>::stackType(int stackSize)
{
if(stackSize<=0)
{
cout<<"The size must be positive"<<endl;
cout<<"creating an array of size 100"<<endl;
maxStackSize=100;
}
else
{
maxStackSize=stackSize;
}
stackTop=0;
list=new Type[maxStackSize];
}
?stackType():拷貝構(gòu)造函數(shù)
template<class Type>
stackType<Type>::stackType(const stackType<Type>& otherStack)
{
list=nullptr; //這里list必須置為空，因?yàn)樵谶@個(gè)程序中，賦值棧的賦值觸發(fā)的是運(yùn)算符重載，而拷貝構(gòu)造函數(shù)只有在作為函數(shù)輸入?yún)?shù)時(shí)或者返回參數(shù)時(shí)才會(huì)被觸發(fā)，同時(shí)由于拷貝構(gòu)造函數(shù)是構(gòu)造函數(shù)重載，所以在觸發(fā)拷貝構(gòu)造函數(shù)前并不會(huì)觸發(fā)構(gòu)造函數(shù)，也意味著并沒(méi)有給list分配內(nèi)存，那么list就是一個(gè)野指針，如果不置為空那么調(diào)用copyStack()時(shí),由于copyStack中第一條語(yǔ)句就是delete []list;刪除沒(méi)有分配內(nèi)存的野指針就會(huì)報(bào)錯(cuò)，所以list置為空是必須的
copyStack(otherStack);
}
operator=():賦值運(yùn)算符重載
template<class Type>
const stackType<Type>& stackType<Type>::operator=(const stackType<Type>& otherStack)
{
if(this!=&otherStack) //避免自我復(fù)制
copyStack(otherStack);
return *this;
}
?~stackType():析構(gòu)函數(shù)
template<class Type>
stackType<Type>::~stackType()
{
delete [] list;
}
?文件構(gòu)成有兩種方式
stackADT單獨(dú)一個(gè)頭文件，stackADT.h，stackType類(lèi)在頭文件stackArr.h中定義，在.cpp文件中實(shí)現(xiàn)。
stackArr.h
#include "stackADT.h" //類(lèi)的定義放在這里
stacArr.cpp
#include<iostream> #include<cassert> #include "stackArr.h" using namespace std; //類(lèi)的實(shí)現(xiàn)放在這里
main.cpp
#include "stackArr.cpp" //這里不能include "stackArr.h"，因?yàn)檫@里是模板類(lèi)，模板類(lèi)需要編譯兩次，
int main()
{
//主函數(shù)的內(nèi)容
return 0;
}
2.把stackArr類(lèi)的定義和實(shí)現(xiàn)都放進(jìn)一個(gè)頭文件stackArr.h
#ifndef H_StackType #define H_StackType #include<iostream> #include<cassert> #include "stackADT" using namespace std; //類(lèi)的定義如下 //此處寫(xiě)類(lèi)的成員函數(shù)的實(shí)現(xiàn) #endif
總結(jié)：使用模板實(shí)現(xiàn)棧的一些要點(diǎn)
首先棧最重要的特征就是先入后出，有一端相當(dāng)于是封閉的，另外棧的一個(gè)重要標(biāo)識(shí)就是棧頂，如果用數(shù)組實(shí)現(xiàn)棧，那么就通過(guò)棧頂元素的索引+1(因?yàn)樗饕龔?開(kāi)始)來(lái)表示棧頂。
2.把對(duì)象復(fù)制過(guò)程進(jìn)行了分離，這里用copyStack函數(shù)實(shí)現(xiàn)了對(duì)象成員變量的復(fù)制，由于成員變量中有指針，而且指針指向的是動(dòng)態(tài)內(nèi)存所以必須進(jìn)行深拷貝，而在拷貝構(gòu)造函數(shù)中直接調(diào)用copyStack函數(shù)即可，同時(shí)這里將賦值運(yùn)算符進(jìn)行了重載，那么對(duì)于語(yǔ)句a=b，調(diào)用的就不是拷貝構(gòu)造函數(shù)了，而是調(diào)用運(yùn)算符重載，只有在作為函數(shù)輸入或者返回參數(shù)時(shí)生成對(duì)象副本次才會(huì)調(diào)用拷貝構(gòu)造函數(shù)，還有析構(gòu)函數(shù)要把內(nèi)存釋放，否則會(huì)導(dǎo)致內(nèi)存泄漏。
3.注意push，pop，top的異常判斷，這也是初學(xué)最容易忽視的點(diǎn)，不要嫌麻煩，對(duì)于會(huì)導(dǎo)致程序出錯(cuò)的輸入要終止程序，像本程序中top函數(shù)是有返回值的所以如果是空棧的話(huà)返回的就是亂碼所以遇到空棧用了assert函數(shù)退出程序，像如果只是輸入不合法，像push函數(shù)，因?yàn)槭窍扰袛嗟臈Ｊ欠褚呀?jīng)滿(mǎn)了，而且沒(méi)有返回值，假如棧已滿(mǎn)，我們不進(jìn)行壓棧操作就行了，只需要在終端打印錯(cuò)誤信息就行，因此就沒(méi)必要終止程序。
4.特別注意類(lèi)模板的定義和實(shí)現(xiàn)，對(duì)于模板類(lèi)而言最好還是把定義和實(shí)現(xiàn)的代碼放在同一個(gè)頭文件，同樣采取類(lèi)內(nèi)聲明，類(lèi)外定義的方法。對(duì)非模板類(lèi)而言，類(lèi)的定義和實(shí)現(xiàn)通常不在同一個(gè)頭文件，一般就是在頭文件中定義類(lèi)，然后在同名的.cpp文件中實(shí)現(xiàn)成員函數(shù)。
[[棧的鏈表實(shí)現(xiàn)]]
到此這篇關(guān)于C++棧的數(shù)組實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++棧的數(shù)組實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)歌曲信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)歌曲信息管理系統(tǒng)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
C語(yǔ)言中access/_access函數(shù)的使用實(shí)例詳解
本文通過(guò)實(shí)例代碼給大家介紹了C語(yǔ)言中access/_access函數(shù)的使用,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-09-09
C++中main函數(shù)怎樣調(diào)用類(lèi)內(nèi)函數(shù)
這篇文章主要介紹了C++中main函數(shù)怎樣調(diào)用類(lèi)內(nèi)函數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
C語(yǔ)言實(shí)現(xiàn)消消樂(lè)游戲的代碼分享
本章我們將編寫(xiě)十字消除游戲，用戶(hù)點(diǎn)擊空白方塊，沿其上下左右方向?qū)ふ业谝粋€(gè)彩色方塊，如果有兩個(gè)或兩個(gè)以上顏色一致，就將其消除，感興趣的可以了解一下2023-02-02
C++?折疊參數(shù)包詳解(悄然增強(qiáng)編程效率)
折疊參數(shù)就是一個(gè)參數(shù)包, 代表是多個(gè)未知,tuple元組就是一個(gè)折疊參數(shù)的使用，這篇文章主要介紹了C++?折疊參數(shù)包悄然增強(qiáng)編程效率,需要的朋友可以參考下2023-05-05
C語(yǔ)言實(shí)現(xiàn)掃雷游戲詳細(xì)代碼實(shí)例
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)掃雷游戲詳細(xì)代碼實(shí)例，有感興趣的同學(xué)可以借鑒參考下2021-02-02
C語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷(xiāo)毀介紹
大家好，本篇文章主要講的是C語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷(xiāo)毀介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下2021-12-12
C++算法設(shè)計(jì)之馬踏棋盤(pán)的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了C++算法設(shè)計(jì)之馬踏棋盤(pán)的實(shí)現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
本文主要介紹了C++11中的智能指針和垃圾回收使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
C++17使用折疊表達(dá)式實(shí)現(xiàn)一個(gè)IsAllTrue函數(shù)的過(guò)程
本文介紹了利用C++17特性實(shí)現(xiàn)IsAllTrue函數(shù)的方法,詳細(xì)講解了從基于初始化列表的初級(jí)版本到使用折疊表達(dá)式和類(lèi)型萃取的高級(jí)優(yōu)化版本,需要的朋友參考下吧2024-09-09