C++棧的數(shù)組實現(xiàn)代碼

更新時間：2022年05月06日 14:20:28 作者：想成為編程高手

這篇文章主要介紹了C++棧的數(shù)組實現(xiàn)方式，本文結(jié)合實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下

棧的抽象數(shù)據(jù)結(jié)構(gòu)。棧的成員函數(shù)需要包括這幾個基本的函數(shù)：initializeStack(),isEmptyStack(),isFullStack,push(),pop(),top()

其功能如下：

initializeStack():初始化棧
isEmptyStack():判斷棧是否為空
isFullStack():判斷棧是否已滿
push():將一個元素壓入棧中
pop():刪除棧頂元素
top():獲得棧頂元素

? C++中用抽象類作為基類實現(xiàn)ADT如下：

template<class Type>
    class stackADT
    {
        virtual void initializeStack()=0;//virtual和=0表明都是純虛函數(shù)，抽象類中只能聲明純虛函數(shù)，不能定義
        virtual bool isEmptyStack() const=0;//const放在函數(shù)后面，表明該函數(shù)是常成員函數(shù)，在函數(shù)執(zhí)行過程中不能改變函數(shù)內(nèi)部變量的值
        virtual bool isFullStack() const=0;
        virtual void push(const Type&)=0;//引用常量，該函數(shù)不會自動對輸入進(jìn)行賦值，同時在函數(shù)內(nèi)的操作也不能改變輸入的值
        virtual void pop()=0;
        virtual Type top() const=0;//這里也采用常成員函數(shù)，因為函數(shù)不會對變量進(jìn)行修改，只是返回變量
    };

? 補(bǔ)充說明：

抽象類：一個類中只要有一個純虛函數(shù)，那么該類就是抽象類，抽象類通常作為基類，純虛函數(shù)在抽象類中只能聲明不能定義。
常成員函數(shù)：什么時候才使用常成員函數(shù)？一般在如果該函數(shù)在執(zhí)行過程中不會有改變變量值的操作，就會把該函數(shù)定義為常成員函數(shù)。
常引用：常引用一般用于函數(shù)輸入，或者函數(shù)返回值。如函數(shù)輸入是常引用類型，那么說明該函數(shù)只會用到引用的值，而不會改變引用變量的值，同時可能引用變量的類型可能很大比較占內(nèi)存，所以用引用可以避免輸入?yún)?shù)的復(fù)制，從而節(jié)約了空間；若函數(shù)返回值為常引用類型，那么有兩個原因，首先const表示返回值不能被修改（注意和常成員函數(shù)做區(qū)分），引用則表示函數(shù)返回時不會對返回變量進(jìn)行拷貝，從而不會觸發(fā)拷貝函數(shù)，因此經(jīng)常被用于運(yùn)算符重載，但是要注意返回值不能是函數(shù)局部變量，因為局部變量在函數(shù)結(jié)束后會被釋放，從而引用了不合法的內(nèi)存，會報錯，像如果是運(yùn)算符重載返回的基本是this指向的對象，這對于函數(shù)來說則是全局的，所以是沒問題的，一般如果返回值是對象，且要避免拷貝，那么就把返回值類型設(shè)置為常引用?？傊米鳛檩斎?yún)?shù)或者返回值時就是為了避免產(chǎn)生副本，而const則是為了保證變量不被修改。
棧的動態(tài)數(shù)組實現(xiàn)

? 直接繼承抽象類，不管是動態(tài)數(shù)組實現(xiàn)還是鏈表實現(xiàn)，抽象類的那幾個成員函數(shù)都是需要的，但是函數(shù)實現(xiàn)的內(nèi)容不一樣

? 這就體現(xiàn)了多態(tài)了。

? 下面是派生棧類的定義：

template <class Type>
    class stackType:public stackADT<Type> //一定要記住每次用到模板類時不要忘記后面的<Type>
    {
        public:
        stackType(int stackSize=100);//注意這里用到了參數(shù)缺省構(gòu)造函數(shù)中的參數(shù)缺省必須在聲明函數(shù)時給出默認(rèn)值而不能在定義函數(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開始)
        void copyStack(const stackType<Type>&);//執(zhí)行深拷貝過程
    };//注意不要忘記分號

? 成員函數(shù)的實現(xiàn)如下：

? initializeStack():

template<class Type>//在類外定義函數(shù)必須使用template，并且每定義一個函數(shù)就要寫一次
void stackType<Type>::initializeStack()  //命名空間也不要忘記::,因為命名空間的名字是模板類，所以后面要有<Type>
{
    stackTop=0;//不需要把元素全部置零，只需要把棧頂元素的索引變成0即可
}

? isEmptyStack():

template<class Type>
bool stackType<Type>::isEmptyStack()const
{
    return !stackTop;//可以認(rèn)為stackTop表示棧中目前元素的個數(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 返回的會是亂碼，push和pop不需要這個操作是因為他們沒有返回值，所以如果不滿足執(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的是一個空指針，那么delete不會執(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必須置為空，因為在這個程序中，賦值棧的賦值觸發(fā)的是運(yùn)算符重載，而拷貝構(gòu)造函數(shù)只有在作為函數(shù)輸入?yún)?shù)時或者返回參數(shù)時才會被觸發(fā)，同時由于拷貝構(gòu)造函數(shù)是構(gòu)造函數(shù)重載，所以在觸發(fā)拷貝構(gòu)造函數(shù)前并不會觸發(fā)構(gòu)造函數(shù)，也意味著并沒有給list分配內(nèi)存，那么list就是一個野指針，如果不置為空那么調(diào)用copyStack()時,由于copyStack中第一條語句就是delete []list;刪除沒有分配內(nèi)存的野指針就會報錯，所以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ú)一個頭文件，stackADT.h，stackType類在頭文件stackArr.h中定義，在.cpp文件中實現(xiàn)。

stackArr.h

#include "stackADT.h"
//類的定義放在這里

stacArr.cpp

#include<iostream>
#include<cassert>
#include "stackArr.h"
using namespace std;
//類的實現(xiàn)放在這里

main.cpp

#include "stackArr.cpp" //這里不能include "stackArr.h"，因為這里是模板類，模板類需要編譯兩次，
int main()
{
    //主函數(shù)的內(nèi)容
    return 0;
}

2.把stackArr類的定義和實現(xiàn)都放進(jìn)一個頭文件stackArr.h

#ifndef H_StackType
#define H_StackType
#include<iostream>
#include<cassert>
#include "stackADT"
using namespace std;
//類的定義如下
//此處寫類的成員函數(shù)的實現(xiàn)
#endif

總結(jié)：使用模板實現(xiàn)棧的一些要點(diǎn)

首先棧最重要的特征就是先入后出，有一端相當(dāng)于是封閉的，另外棧的一個重要標(biāo)識就是棧頂，如果用數(shù)組實現(xiàn)棧，那么就通過棧頂元素的索引+1(因為索引從0開始)來表示棧頂。

2.把對象復(fù)制過程進(jìn)行了分離，這里用copyStack函數(shù)實現(xiàn)了對象成員變量的復(fù)制，由于成員變量中有指針，而且指針指向的是動態(tài)內(nèi)存所以必須進(jìn)行深拷貝，而在拷貝構(gòu)造函數(shù)中直接調(diào)用copyStack函數(shù)即可，同時這里將賦值運(yùn)算符進(jìn)行了重載，那么對于語句a=b，調(diào)用的就不是拷貝構(gòu)造函數(shù)了，而是調(diào)用運(yùn)算符重載，只有在作為函數(shù)輸入或者返回參數(shù)時生成對象副本次才會調(diào)用拷貝構(gòu)造函數(shù)，還有析構(gòu)函數(shù)要把內(nèi)存釋放，否則會導(dǎo)致內(nèi)存泄漏。

3.注意push，pop，top的異常判斷，這也是初學(xué)最容易忽視的點(diǎn)，不要嫌麻煩，對于會導(dǎo)致程序出錯的輸入要終止程序，像本程序中top函數(shù)是有返回值的所以如果是空棧的話返回的就是亂碼所以遇到空棧用了assert函數(shù)退出程序，像如果只是輸入不合法，像push函數(shù)，因為是先判斷的棧是否已經(jīng)滿了，而且沒有返回值，假如棧已滿，我們不進(jìn)行壓棧操作就行了，只需要在終端打印錯誤信息就行，因此就沒必要終止程序。

4.特別注意類模板的定義和實現(xiàn)，對于模板類而言最好還是把定義和實現(xiàn)的代碼放在同一個頭文件，同樣采取類內(nèi)聲明，類外定義的方法。對非模板類而言，類的定義和實現(xiàn)通常不在同一個頭文件，一般就是在頭文件中定義類，然后在同名的.cpp文件中實現(xiàn)成員函數(shù)。
[[棧的鏈表實現(xiàn)]]

到此這篇關(guān)于C++棧的數(shù)組實現(xiàn)的文章就介紹到這了,更多相關(guān)C++棧的數(shù)組實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: