導(dǎo)言
大家好，很高興又和大家見(jiàn)面啦?。?！
在上一個(gè)篇章中，我們介紹了棧的基本概念，以及棧中的重要術(shù)語(yǔ)。通過(guò)介紹我們知道了棧的本質(zhì)也是一種線性表，只不過(guò)它是一種操作受限的線性表。因此棧的實(shí)現(xiàn)方式與線性表的實(shí)現(xiàn)實(shí)際上是大同小異的。下面我們就來(lái)介紹一下如何通過(guò)C語(yǔ)言實(shí)現(xiàn)棧。
一、棧的分類
棧作為一種操作受限的線性表，它在存儲(chǔ)時(shí)根據(jù)存儲(chǔ)方式的不同，分為兩類——順序棧與鏈棧。
下面我們將來(lái)介紹第一類?！樞驐５腃語(yǔ)言實(shí)現(xiàn)；
二、順序棧
通過(guò)順序存儲(chǔ)的線性表我們稱為順序表，同樣，通過(guò)順序存儲(chǔ)的棧我們將其稱為順序棧。
順序棧是利用一組地址連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針(top)指示當(dāng)前棧頂元素的位置。
2.1 順序棧的數(shù)據(jù)類型
地址連續(xù)的存儲(chǔ)單元相信大家都已經(jīng)不陌生了。在順序表中，我們通過(guò)數(shù)組實(shí)現(xiàn)了靜態(tài)的順序表，通過(guò)malloc與calloc函數(shù)實(shí)現(xiàn)了動(dòng)態(tài)的順序表。在棧的實(shí)現(xiàn)中，我們不妨借鑒順序表的實(shí)現(xiàn)方式來(lái)實(shí)現(xiàn)棧，因此順序棧的數(shù)據(jù)類型我們可以描述為：
//順序棧的數(shù)據(jù)類型基本格式
#define MaxSize 10//定義棧中元素的最大個(gè)數(shù)
typedef struct SqStack {
ElemType data[MaxSize];//存放在棧中的元素
int top;//棧頂指針
}SqStack;
//ElemType——存放元素的數(shù)據(jù)類型
//top——棧頂元素的下標(biāo)
//SqStack——棧的數(shù)據(jù)類型
對(duì)于順序棧而言，它的實(shí)現(xiàn)就是通過(guò)靜態(tài)數(shù)組的方式進(jìn)行實(shí)現(xiàn)的，因此，順序棧會(huì)有一下幾個(gè)特點(diǎn)：
- 棧的大小無(wú)法更改；
- 進(jìn)棧操作會(huì)受限制，當(dāng)進(jìn)棧的元素個(gè)數(shù)大于棧能存儲(chǔ)的元素最大個(gè)數(shù)時(shí)，會(huì)出現(xiàn)棧溢出的問(wèn)題；
- 由于進(jìn)棧操作只能從棧頂進(jìn)行，因此在實(shí)現(xiàn)棧時(shí)我們有兩種方式實(shí)現(xiàn)：
- 從下標(biāo)0開(kāi)始，依次入棧，下標(biāo)0為棧的棧底；
- 從下標(biāo)
MaxSize-1開(kāi)始，依次入棧，下標(biāo)MaxSize-1為棧的棧底；
接下來(lái)我們來(lái)看一下順序棧的初始化；
2.2 順序棧的初始化
我們?cè)趯?duì)順序棧進(jìn)行初始化時(shí)，首先要明確我們要初始化的對(duì)象。從數(shù)據(jù)類型中可知，順序棧中除了存儲(chǔ)元素的靜態(tài)數(shù)組外，還有一個(gè)存儲(chǔ)棧頂元素下標(biāo)的棧頂指針。
對(duì)于空棧而言，靜態(tài)數(shù)組中存儲(chǔ)的內(nèi)容并不重要，因?yàn)槲覀儾⒉粫?huì)訪問(wèn)這些內(nèi)容，因此，我們需要初始化的對(duì)象就是順序棧的棧頂指針。
為了幫助大家更好的理解順序棧的初始化操作，我們以從下標(biāo)0為棧底的方式來(lái)介紹初始化的實(shí)現(xiàn)。
由于棧頂指針指向的是棧中的棧頂元素，存儲(chǔ)的是棧頂元素的數(shù)組下標(biāo)，因此，當(dāng)棧為空棧時(shí)，棧頂指針我們只需要將其初始化為-1就行，如下所示：
//順序棧的初始化
bool InitStack(SqStack* S) {
if (!S)
return false;
S->top = -1;
return true;
}
由于這里的形參是指針，因此我們?cè)谑褂们靶枰獙?duì)指針進(jìn)行判空操作，如果指針為空指針時(shí)，函數(shù)將返回false，當(dāng)指針不為空指針時(shí)，此時(shí)我們就可以正常的對(duì)棧頂指針進(jìn)行初始化了；
2.3 棧的判空
我們想知道一個(gè)棧是否為空棧時(shí)，我們就可以根據(jù)棧頂指針的初始化我進(jìn)行判空，在初始化時(shí)，我們將棧頂指針初始化為-1，那么我們?cè)谂锌諘r(shí)就可以判斷此時(shí)的棧頂指針是否為-1，如下所示：
//順序棧的判空操作
bool StackEmpty(SqStack S) {
if (S.top == -1)
return true;
return false;
}
因?yàn)槲覀兇藭r(shí)只是判斷一下棧的情況，并未對(duì)棧有任何的修改，所以我們?cè)趥鲄r(shí)，只需要通過(guò)傳值傳參即可，此時(shí)的形參只是對(duì)實(shí)參的一份臨時(shí)拷貝，我們對(duì)形參的任何操作都不會(huì)影響實(shí)參；
2.5 順序棧的進(jìn)棧
當(dāng)我們創(chuàng)建好一個(gè)順序棧后，我們就可以通過(guò)進(jìn)棧操作來(lái)將元素存入順序棧中，由于空棧時(shí)棧頂指針存儲(chǔ)的下標(biāo)為-1，因此我們?cè)诖娣旁厍靶枰驅(qū)ｍ斨羔樦赶虼娣艞ｍ斣氐目臻g，即對(duì)棧頂指針進(jìn)行+1操作，如下所示：
//順序棧的入棧操作
bool Push(SqStack* S, ElemType x) {
//判斷指針S是否為空以及棧頂指針是否存滿
if (!S || S->top == MaxSize - 1)
return false;
//棧頂指針向上移動(dòng)
S->top += 1;
//將數(shù)據(jù)存入棧頂
S->data[S->top] = x;
return true;
}
為了確保我們能夠順利的將數(shù)據(jù)存入棧中，我們?cè)谶M(jìn)行入棧操作前需要先判斷此時(shí)的指針S是否為空指針，如果是空指針，那說(shuō)明傳參出現(xiàn)了問(wèn)題。在確定S不為空指針后，我們還要進(jìn)一步判斷是否為滿棧，即棧頂指針存儲(chǔ)的下標(biāo)為MaxSize-1；
當(dāng)然這里我們可以對(duì)代碼進(jìn)行一下簡(jiǎn)化，從實(shí)現(xiàn)的順序我們可以看到，我們是先對(duì)棧頂指針進(jìn)行+1操作，然后再使用的棧頂指針，那也就是先+1再使用，C語(yǔ)言中的前置++這個(gè)操作符剛好滿足這個(gè)特性，因此這里我們就可以將移動(dòng)與存入合并為一條代碼，如下所示：
//順序棧的入棧操作
bool Push(SqStack* S, ElemType x) {
//判斷指針S是否為空以及棧頂指針是否存滿
if (!S || S->top == MaxSize - 1)
return false;
//先移動(dòng)棧頂指針，再使用
S->data[++(S->top)] = x;
return true;
}
在了解了進(jìn)棧操作后，下面我們來(lái)看一下順序棧是如何進(jìn)行出棧操作的；
2.6 順序棧的出棧
不知道大家還記不記得棧的操作特性——后進(jìn)先出(LIFO)，也就是后進(jìn)棧的元素會(huì)先一步出棧，正是因?yàn)檫@個(gè)特性，所以我們?cè)谶M(jìn)行出棧操作時(shí)，只能從棧頂元素開(kāi)始進(jìn)行出棧，每次彈出一個(gè)元素后，棧頂指針都需要往下移動(dòng)一位，如下所示：
//順序棧的出棧操作
bool Pop(SqStack* S, ElemType* x) {
if (!S || !x || S->top > -1)
return false;
//彈出元素
*x = S->data[S->top];
//棧頂指針向下一定
S->top -= 1;
return true;
}
出棧操作和入棧操作一樣都是需要對(duì)棧進(jìn)行修改，所以這里是通過(guò)傳址傳參完成的出棧，這里有一個(gè)點(diǎn)，因?yàn)槲覀円獙棾龅脑胤祷氐街骱瘮?shù)中，所以對(duì)于存儲(chǔ)彈出數(shù)據(jù)的變量x我們也是通過(guò)傳址的形式進(jìn)行傳參。
同樣為了順利的完成出棧操作，我們需要對(duì)指針S與指針x進(jìn)行判空操作，以確保傳參的正確性，同時(shí)我們還要確保棧不為空棧。
從出棧的操作順序我們可以看到，對(duì)于棧頂指針，我們是先使用，再對(duì)其進(jìn)行-1的操作，在C語(yǔ)言中后置–這個(gè)操作符剛好也是符合這個(gè)規(guī)則，因此這里我們可以將其改寫(xiě)為：
//順序棧的出棧操作
bool Pop(SqStack* S, ElemType* x) {
if (!S || !x || S->top > -1)
return false;
//先使用，后移動(dòng)棧頂指針
*x = S->data[S->top--];
return true;
}
現(xiàn)在我們已經(jīng)實(shí)現(xiàn)了增加、刪除的操作，那對(duì)于棧的元素我們應(yīng)該如何查找呢？
2.7 順序棧的查找
對(duì)于棧而言，因?yàn)闂５膯蜗虿僮魈匦裕@就導(dǎo)致我們無(wú)法越過(guò)棧頂指針去查看棧中存儲(chǔ)的其它元素，因此，我們對(duì)棧的查找實(shí)質(zhì)上就是對(duì)棧頂指針的查找，在找到棧頂指針后將棧頂元素返回給主函數(shù)，如下所示：
//順序棧的查找
bool GetTop(SqStack S, ElemType* x) {
if (!x || S.top == -1)
return false;
//返回棧頂元素
*x = S.data[S.top];
return true;
}
對(duì)于查找操作而言，因?yàn)橐獛Щ貤ｍ斣氐木唧w數(shù)據(jù)，因此這里對(duì)于存儲(chǔ)棧頂元素的參數(shù)x我們是通過(guò)指針進(jìn)行接收，也就是此時(shí)的實(shí)參是以傳址的方式進(jìn)行的傳參，而且我們?cè)诓檎也僮髦胁⒉粫?huì)修改棧，所以我們只需要對(duì)棧有一份臨時(shí)拷貝就行，可以看到對(duì)于形參S，我們是以傳值的方式進(jìn)行傳參。
為了能夠順利的進(jìn)行查找，我們也是需要對(duì)指針x與棧頂指針進(jìn)行判斷：
- 當(dāng)指針x為空指針時(shí)，表示此時(shí)傳參出現(xiàn)了問(wèn)題；
- 當(dāng)棧頂指針為-1時(shí)，表示此時(shí)的棧為空棧；
在這兩種情況下我們都應(yīng)該給使用者一個(gè)反饋，因此這里就是通過(guò)返回false來(lái)告知使用者。
下面我們思考一個(gè)問(wèn)題——我們?cè)诔跏蓟瘯r(shí)能不能將棧頂指針初始化為0呢？答案是可以的。下面我們就來(lái)看一下初始化為0時(shí)的順序棧有何改動(dòng)；
2.8 順序棧的另一種實(shí)現(xiàn)方式
我們?cè)趯ｍ斨羔槼跏蓟癁?時(shí)我們需要先明確此時(shí)棧頂指針的含義——棧中已經(jīng)存儲(chǔ)的元素個(gè)數(shù)，如下圖所示：
從圖中我們可以看到，當(dāng)棧頂指針初始化為-1時(shí)，此時(shí)的棧頂指針指向的就是棧頂元素，而當(dāng)棧頂指針初始化為0時(shí)，棧頂指針指向的是棧頂元素上方的空間，在這種情況下操作上面會(huì)有以下改動(dòng)：
- 初始化——在初始化時(shí)，棧頂指針的值需要有-1改為0；
//順序棧的初始化
bool InitStack(SqStack* S) {
if (!S)
return false;
S->top = 0;
return true;
}
- 判滿——在進(jìn)行入棧操作前，對(duì)棧進(jìn)行判滿操作時(shí)由原先的MaxSize-1改為MaxSize；
//順序棧的入棧操作
bool Push(SqStack* S, ElemType x) {
//判斷指針S是否為空以及棧頂指針是否存滿
if (!S || S->top == MaxSize)
return false;
}
- 入?！谶M(jìn)行入棧操作時(shí)，由原先的先移動(dòng)棧頂指針，再存入數(shù)據(jù)改為先存入數(shù)據(jù)后移動(dòng)指針；
//順序棧的入棧操作
bool Push(SqStack* S, ElemType x) {
//判斷指針S是否為空以及棧頂指針是否存滿
if (!S || S->top == MaxSize - 1)
return false;
//將數(shù)據(jù)存入棧頂
S->data[S->top] = x;
//棧頂指針向上移動(dòng)
S->top += 1;
//可簡(jiǎn)寫(xiě)為
S->data[S->top++] = x;
return true;
}
- 判空——我們?cè)趯?duì)棧進(jìn)行判空操作時(shí)由原先的判斷棧頂指針是否為-1改為棧頂指針是否為0；
//順序棧的判空操作
bool StackEmpty(SqStack S) {
if (S.top == 0)
return true;
return false;
}
- 出?！谂锌胀旰髮?duì)棧進(jìn)行出棧操作時(shí)，我們需要將先彈出數(shù)據(jù)后移動(dòng)指針改為先移動(dòng)指針后彈出數(shù)據(jù)；
//順序棧的出棧操作
bool Pop(SqStack* S, ElemType* x) {
if (!S || !x || S->top > -1)
return false;
//棧頂指針向下一定
S->top -= 1;
//彈出元素
*x = S->data[S->top];
//可簡(jiǎn)寫(xiě)為
*x = S->data[--S->top];
return true;
}
- 查找——在對(duì)棧頂元素進(jìn)行查找時(shí)，我們需要將直接查找改為先移動(dòng)指針，再查找；
//順序棧的查找
bool GetTop(SqStack S, ElemType* x) {
if (!x || S.top == -1)
return false;
//返回棧頂元素
*x = S.data[--S.top];
return true;
}
對(duì)于第一種初始化為-1的方式，我們?cè)诓檎覘ｍ斣貢r(shí)會(huì)更加的方便；而第二種初始化為0的方式，我們?cè)谶M(jìn)行判空和判滿時(shí)會(huì)對(duì)棧中已經(jīng)存儲(chǔ)的元素個(gè)數(shù)更加的清晰。這兩種創(chuàng)建方式各有各的好處，大家可以根據(jù)自己的喜好來(lái)進(jìn)行選擇，但是一定要注意在進(jìn)行進(jìn)棧與出棧操作時(shí)的邏輯順序不要弄反咯。
2.9 順序棧的銷毀
對(duì)于棧的銷毀，實(shí)質(zhì)上就是將棧中的元素從棧頂依次彈出，最后釋放棧的空間，這里我們可以通過(guò)循環(huán)來(lái)完成該操作，如下所示：
//順序棧的銷毀
bool DestroyStack(SqStack* S) {
if (!S)
return false;
while (S->top > -1) {
S->top--;//棧頂指針往下移動(dòng)
}
return true;
}
當(dāng)我們初始化是將棧頂指針初始化為0時(shí)，對(duì)應(yīng)的循環(huán)判斷條件我們只需要改成>0就可以了，由于順序棧是通過(guò)靜態(tài)數(shù)組的方式實(shí)現(xiàn)的，我們不能像鏈表以及動(dòng)態(tài)順序表一樣通過(guò)free函數(shù)來(lái)完成銷毀操作，只能夠在程序完成后有系統(tǒng)自動(dòng)進(jìn)行內(nèi)存回收的操作，這里我就不多加贅述了。
結(jié)語(yǔ)
現(xiàn)在對(duì)于順序棧的基本C語(yǔ)言實(shí)現(xiàn)我們就全部介紹完了，希望這篇內(nèi)容能幫助大家更好的學(xué)習(xí)和理解順序棧的相關(guān)知識(shí)點(diǎn)。在下一篇內(nèi)容中，我們會(huì)介紹如何通過(guò)C語(yǔ)言實(shí)現(xiàn)共享?xiàng)?，大家記得關(guān)注哦！文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-802946.html
最后感謝各位的翻閱，咱們下一篇再見(jiàn)！?。?span toymoban-style="hidden">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-802946.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言實(shí)現(xiàn)順序棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
