零零總總搜索了一些關(guān)于鏈棧的資料，了解了鏈棧的基本操作，一直覺(jué)得別人寫(xiě)的代碼或多或少存在一些問(wèn)題，所以打算自己寫(xiě)一篇關(guān)于鏈棧的文章，也算是對(duì)所學(xué)知識(shí)的梳理和鞏固了。

首先說(shuō)明本文使用C語(yǔ)言進(jìn)行鏈棧的基本操作，鏈棧是無(wú)頭結(jié)點(diǎn)的。這里補(bǔ)充說(shuō)明一下，無(wú)頭結(jié)點(diǎn)的意思是，鏈棧的頭結(jié)點(diǎn)是存儲(chǔ)數(shù)據(jù)的，有頭結(jié)點(diǎn)的是頭結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)的，不了解的小伙伴可以先去學(xué)習(xí)一下單鏈表的內(nèi)容。

之所以在這里說(shuō)明，是因?yàn)槲铱催^(guò)不少文章寫(xiě)的鏈棧是帶頭結(jié)點(diǎn)，有的還分不清到底有沒(méi)有頭結(jié)點(diǎn)，導(dǎo)致我在學(xué)習(xí)的時(shí)候浪費(fèi)了不少時(shí)間，廢話(huà)不多說(shuō)，以下進(jìn)入正題。

鏈棧的基本操作包括以下幾點(diǎn)：

a. 棧的初始化

b. 棧的判空

c. 入棧

d. 出棧

e. 讀棧頂元素

f. 遍歷棧

g. 銷(xiāo)毀棧

定義一個(gè)結(jié)構(gòu)體，用來(lái)構(gòu)造鏈棧。

typedef struct StackNode{
    int data;//數(shù)據(jù)域，用來(lái)存放數(shù)據(jù)
    StackNode *next;//指針域，用來(lái)指向棧頂?shù)南乱粋€(gè)元素
}LinkStack;
LinkStack *LS;//定義一個(gè)LinkStack類(lèi)型的指針

一、初始化棧

鏈棧初始化首先要構(gòu)造一個(gè)空棧，先創(chuàng)建一個(gè)頭結(jié)點(diǎn)，然后讓該頭結(jié)點(diǎn)的指針指向空，這里使用傳參的方式初始化棧。

void StackInit(LinkStack* &S)//這里傳入的參數(shù)是一個(gè)指針
{                            //要對(duì)傳入的參數(shù)進(jìn)行賦值操作，需要加一個(gè)取址符
    S = NULL;//直接讓S指向空，不能在這里像下面注釋的代碼一樣分配空間，否則無(wú)法完成判空操作
    /*S = (LinkStack *)malloc(sizeof(LinkStack *))；
    if(S == NULL)
    {
        printf("Malloc Error!!!\n");
        return false;
    }
    S->next = NULL;
    return true;*/
}

二、棧的判空

直接判斷棧頂?shù)牡刂肥欠駷榭?/p>

bool StackIsEmpty(LinkStack* S)
{
    if(S == NULL)
        return true;
    return false;
}

三、入棧

入棧需要判斷是否為空，若為空棧，第一個(gè)入棧元素為棧頂，沒(méi)有下一元素，指向下一個(gè)元素的指針為空。

bool Stack_Push(LinkStack* &S,int PushData)
{
    if(S == NULL)//若棧為空
    {    
        S = (LinkStack *)malloc(sizeof(LinkStack));
        if(S == NULL)
        {
            printf("Malloc Error!!!\n");
            return false;
        }
        S->data = PushData;//給頭結(jié)點(diǎn)賦值
        S->next = NULL;//沒(méi)有下一個(gè)元素，指向空
        return true;
    }
    //棧不為空
    LinkStack *NewNode = (LinkStack)malloc(sizeof(LinkStack));
    if(NewNode == NULL)
    {
        printf("Malloc Error!!!\n");
        return false;
    }
    NewNode->data = S->data;//用新節(jié)點(diǎn)存儲(chǔ)當(dāng)前棧頂元素，包括指針
    NewNode->next = S->next;//讓NewNode成為當(dāng)前棧頂
    S->next = NewNode;//S的下一個(gè)元素為NewNode,S成為新的棧頂（S仍為棧頂）
    S->data = PushData;//記錄入棧元素
    return true;
}

四、出棧

出棧即為刪除棧頂

bool Stack_Pop(LinkStack* &S,int &PopData)//PopData用于記錄出棧元素
{
    if(S == NULL)//棧為空
? ? {
? ? ? ? printf("Stack Is Empty!!!\n");
? ? ? ? return false;
? ? }

? ? if(S->next == NULL)//最后一個(gè)元素
    {
        PopData = S->data;
        free(S);//釋放空間
        S = NULL;//防止成為野指針
        return true;
    }
    
    PopData = S->data;//通過(guò)PopData獲取出棧（棧頂）數(shù)據(jù)
    
? ? /*? ? 此處為寫(xiě)錯(cuò)部分的代碼
? ? LinkStack *TempNode = S->next;//出棧需要釋放棧頂，需要定義一個(gè)臨時(shí)變量
    
? ? S->next = TempNode->next;//棧頂元素出棧，下一個(gè)元素成為新的棧頂
    S->data = TempNode->data;
? ? */

? ? LinkStack *TempNode = S;//出棧需要釋放棧頂，需要定義一個(gè)臨時(shí)變量,存放舊棧頂?shù)牡刂泛椭羔樣?? ? 
? ? //此時(shí)TempNode為棧頂，其指向的下一個(gè)棧元素應(yīng)為新的棧頂
    S = TempNode->next;//棧頂元素出棧，下一個(gè)元素成為新的棧頂
    S->data = TempNode->next->data;

    free(TempNode);//釋放舊棧頂空間
    TempNode = NULL;//防止成為野指針

    return true;
}

五、讀取棧頂元素

讀取棧頂元素不同于出棧，只需要讀取棧頂元素，不需要釋放棧頂空間

bool Stack_Read(LinkStack* S,int &PopData)//PopData用于記錄出棧元素
{
? ? if(S == NULL)//棧為空，沒(méi)有元素可讀，返回false
? ? {
? ? ? ? printf("Stack Is Empty!!!\n");
? ? ? ? return false;
? ? }
? ? PopData = S->data;
? ? return;
}

六、遍歷棧

這里直接打印棧的所有元素，從棧頂?shù)綏５?/p>

//遍歷棧
void Stack_Traverse(LinkStack* S)
{
? ? if(S == NULL)//棧為空
? ? {
? ? ? ? printf("Stack Is Empty!!!\n");
? ? ? ? return;
? ? }
? ? if(S->next == NULL)//只有一個(gè)元素
? ? {
? ? ? ? printf("StackTop to StackBottom: %d\n",S->data);
? ? ? ? return;
? ? }
? ? LinkStack *p,*q;
? ? p = S;//p為q是上一個(gè)元素
? ? q = p->next;//q為p的下一個(gè)元素
? ? printf("StackTop to StackBottom: ");
? ? while(q->next != NULL)
? ? {
? ? ? ? printf("%d ",p->data);
? ? ? ? p = p->next;
? ? ? ? q = p->next;
? ? }
? ? printf("%d %d\n",p->data,q->data);
}

七、銷(xiāo)毀棧

void Stack_Destroy(LinkStack* &S)
{
? ? LinkStack *p = NULL;
? ? while(S != NULL)
? ? {
? ? ? ? P = S;
? ? ? ? S = S->next;
? ? ? ? free(p);
? ? }
? ? p = NULL;
? ? S = NULL;
}

需要注意的是，在釋放?？臻g之后，需要將相應(yīng)的指針指向空，否則將會(huì)成為野指針，并且書(shū)寫(xiě)也不規(guī)范。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過(guò)程中我查閱了許多資料，發(fā)現(xiàn)許多博客的代碼存在這樣的問(wèn)題，這讓有那么一點(diǎn)強(qiáng)迫癥的我看的很不舒服，所以就打算自己寫(xiě)。

本文是我第一次寫(xiě)、第一次發(fā)表的文章，內(nèi)容很少，也很簡(jiǎn)潔，代碼完全是在網(wǎng)頁(yè)敲出來(lái)，就看著偽代碼敲，有什么不對(duì)的請(qǐng)給位看官批評(píng)指正，謝謝！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-450129.html