一、棧的介紹前面學(xué)習(xí)的線性表中包含順序表和鏈表，這兩種數(shù)據(jù)結(jié)構(gòu)允許在任意位置進(jìn)行插入和刪除，那么有沒有一種數(shù)據(jù)結(jié)構(gòu)是不能在任意位置進(jìn)行插入刪除，而只允許在一邊進(jìn)行插入刪除的呢？？當(dāng)然有的，這就是我們今天要學(xué)習(xí)的一種新的數(shù)據(jù)結(jié)構(gòu)：棧
棧是一種只允許在一端進(jìn)行插入刪除的數(shù)據(jù)結(jié)構(gòu)，插入刪除的一端叫做棧頂，不能進(jìn)行插入刪除的一端叫做棧底。
通常情況下，為了能夠方便的修改數(shù)據(jù)結(jié)構(gòu)中存放的數(shù)據(jù)類型，我們會對數(shù)據(jù)類型進(jìn)行重定義
在學(xué)習(xí)任何的數(shù)據(jù)結(jié)構(gòu)的時候，最重要的首先是要了解這個數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)，既然棧是一種數(shù)據(jù)結(jié)構(gòu)，那么就說明?？梢杂脕泶鎯?shù)據(jù)，所以棧的結(jié)構(gòu)中一定包含一個數(shù)據(jù)域，由于棧需要不斷對棧頂元素進(jìn)行出棧，所以需要一個標(biāo)記棧頂元素的指針，這個指針是一個數(shù)組下標(biāo)，也就是一個整數(shù)，綜合這兩種，我們覺得數(shù)據(jù)域設(shè)置成數(shù)組能夠方便的處理這個問題。由于是數(shù)組，如果是靜態(tài)數(shù)組，就導(dǎo)致數(shù)組的容量不能變，容量太小，會導(dǎo)致不夠，容量太大，導(dǎo)致空間浪費(fèi)。因此，我們覺得動態(tài)數(shù)組（能夠進(jìn)行擴(kuò)容的數(shù)組）能夠方便處理以上問題。動態(tài)數(shù)組就涉及到擴(kuò)容的問題，所以肯定需要一個變量來記錄數(shù)組中的容量。
在上述的結(jié)構(gòu)中，val表示棧的數(shù)據(jù)域，是一個動態(tài)的數(shù)組，top表示棧頂指針，能夠標(biāo)識棧頂元素的情況（可以有兩種表示方法），capacity表示棧中的容量大小。
這里需要注意一個點：top能夠表示棧頂元素的情況，是數(shù)組的下標(biāo)，其初始狀態(tài)可以是兩種表示方法
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的另一個核心就是學(xué)習(xí)如何對這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作
1. 常見函數(shù)接口的聲明
在上面的聲明中，我們發(fā)現(xiàn)函數(shù)參數(shù)中傳的是棧的結(jié)構(gòu)體地址，這是為啥呢？
我們知道棧的結(jié)構(gòu)本質(zhì)是一個結(jié)構(gòu)體，而結(jié)構(gòu)體一般都是很大的，同時，我們在函數(shù)體中有時可能需要對棧中的內(nèi)容進(jìn)行修改，比如入棧和出棧，就需要改變棧中的內(nèi)容，如果傳的是棧的結(jié)構(gòu)體，那么在函數(shù)的形參中我們知道是一份實參的拷貝，所以對形參的改變是不會影響實參的，那么我們考慮傳結(jié)構(gòu)體的地址，通過結(jié)構(gòu)體的地址，函數(shù)就可以通過指針找到真正想改變的內(nèi)容。
因此，傳結(jié)構(gòu)體的地址的好處有兩個：
初始化函數(shù)是根據(jù)數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)來實現(xiàn)的，我們知道棧中包含一個動態(tài)數(shù)組的指針和一個棧頂指針（數(shù)組下標(biāo)）和一個容量，動態(tài)數(shù)組剛開始啥數(shù)據(jù)都沒有，我們只需要對其置成空指針即可，防止出現(xiàn)野指針，棧頂指針指向的是棧頂元素在數(shù)組中的下標(biāo)的下一個位置，即新元素入棧時所在的位置，當(dāng)棧為空的時候，棧頂指針指向0，剛開始的容量就是0
（2）銷毀棧
銷毀棧函數(shù)主要是完成對棧中申請的空間進(jìn)行釋放，注意在我們不想要使用這個棧的時候，一定要記得對棧進(jìn)行銷毀，本質(zhì)就是對棧中開辟的數(shù)組進(jìn)行釋放，防止出現(xiàn)內(nèi)存泄露。
（3）入棧
入棧時一定要考慮棧是否已經(jīng)滿了，如果已經(jīng)滿了，則需要進(jìn)行擴(kuò)容，擴(kuò)容時在確定新容量的時候一定要注意原先棧中的容量是否為0（初始化狀態(tài)），這種情況需要進(jìn)行特殊處理。擴(kuò)容完成之后就是將數(shù)據(jù)插入棧頂，因為top表示的是棧頂元素的下一個位置，所以是先將元素入棧到top位置，再將top++。
出棧的本質(zhì)就是刪除棧頂元素，在出棧的時候一定要注意棧是否為空，當(dāng)st->top>0時才可以進(jìn)行刪除數(shù)據(jù)，刪除的時候并不是真的將該數(shù)據(jù)從內(nèi)存中移除，而是將棧頂指針往前移一位即可。棧中的top其實標(biāo)識也可以是棧中的有效數(shù)據(jù)，因為剛開始棧為空的時候，top為0，標(biāo)識沒有數(shù)據(jù)，每次在入棧的時候，插入數(shù)據(jù)之后都會對top進(jìn)行++操作，每次刪除棧頂元素的時候，都會對top進(jìn)行–的操作，所以棧中的top可以標(biāo)識棧中的有效數(shù)據(jù)個數(shù)。
返回棧頂元素函數(shù)中，也要注意棧是否為空，如果棧為空，無法返回棧頂元素，這里需要注意，因為top表示的是棧頂元素的下一個位置，所以返回的是top的前一個位置的值，而不是返回top位置的值。這個函數(shù)在遍歷訪問棧的時候是很重要的。
當(dāng)棧頂指針指向0的時候表示現(xiàn)在棧是空的狀態(tài)，即初始化狀態(tài)。這個函數(shù)在遍歷訪問棧的時候也是很重要的。
當(dāng)棧為空的時候，top = 0，每次入棧的時候，top++,出棧的時候top–,所以top可以很好地表示棧的數(shù)據(jù)個數(shù)
在上面的函數(shù)定義中，我們發(fā)現(xiàn)每一個函數(shù)都需要對棧的結(jié)構(gòu)體指針進(jìn)行斷言操作，這是為啥？
在函數(shù)的操作中，我們知道函數(shù)中需要通過棧的結(jié)構(gòu)體指針找到棧中的內(nèi)容，也就是需要對棧的結(jié)構(gòu)體指針進(jìn)行解引用，因此，這個結(jié)構(gòu)體指針是一定不能為空的，否則就會出現(xiàn)空指針的解引用從而使程序崩潰。
使用棧的時候，一定需要注意幾點：首先是創(chuàng)建棧的結(jié)構(gòu)體，接下來，通過這個棧的結(jié)構(gòu)體的地址對棧中的內(nèi)容進(jìn)行處理：處理首先是對棧進(jìn)行初始化，就是可以插入和刪除數(shù)據(jù)，當(dāng)棧中擁有一定的數(shù)據(jù)的時候，這個時候我們可以遍歷訪問棧中的數(shù)據(jù)，這個通常需要使用的函數(shù)有判空函數(shù)，返回棧頂元素函數(shù)，出棧函數(shù)，當(dāng)我們使用完棧之后，不想再使用的時候需要對棧進(jìn)行銷毀，防止出現(xiàn)內(nèi)存泄露。
1.
從上面的測試代碼中，我們要學(xué)習(xí)棧的基本使用：先定義一個棧的結(jié)構(gòu)體，再對這個棧進(jìn)行初始化操作，后面再進(jìn)行各種常見的操作。除此之外，我們還需要學(xué)習(xí)棧的遍歷思路：需要一個循環(huán)來解決，當(dāng)棧不為空時，先訪問棧的棧頂元素，再出棧。
2.
提交代碼：
重慶分公司
重慶分公司
bool isValid(char * s){// 需要一個棧
// 創(chuàng)建并初始化棧
Stack st;
StackInit(&st);
// 正常使用棧
while(*s)
{if(*s == '('||*s == '{'||*s == '[')
{// 左括號，入棧
StackPush(&st,*s);
}
else
{// 右括號：出棧
// 出棧時需要判斷此時棧是否為空，如果棧為空，則匹配失敗
if(StackEmpty(&st))
{// 此時徐奧入棧，但是棧為空，所以匹配失敗
return false;
}
else
{// 棧不為空，出棧頂元素進(jìn)行匹配，匹配失敗，則返回false;
char retTop = StackTop(&st);
StackPop(&st);
if(*s == ')'&&retTop!='('||*s == '}'&&retTop!='{'||*s == ']'&&retTop!='[')
{// 當(dāng)出棧的括號和遍歷到的右括號不匹配的時候，匹配失敗
return false;
}
}
}
s++;
}
return StackEmpty(&st);
}提交結(jié)果：
思路分析：
本題中采用構(gòu)造一個棧來解決問題，遍歷給定的字符串，遍歷到的括號可能是左括號也可能是右括號。當(dāng)遇到左括號時，直接入棧，當(dāng)遇到右括號時，出棧頂元素和此時的右括號進(jìn)行匹配，此時棧中可能為空也可能不為空，如果棧此時為空，則無法匹配，返回false。如果棧不為空，則出棧頂元素進(jìn)行匹配，如果匹配，繼續(xù)向后遍歷字符串，如果不匹配，則此時返回false。當(dāng)遍歷完字符串之后，需要檢查此時棧是否為空，因為可能會出現(xiàn)棧中還有多余的左括號的情況，如果棧為空，則成功匹配，返回true,如果棧不為空，則匹配失敗，返回false。
綜合上面的處理，我們可以知道，題目給定的字符串可能出現(xiàn)的情況：
- 為空
- 正常的情況，匹配成功的
- 遇到第一個就是右括號，匹配失敗
- 遇到第一個是左括號，還沒發(fā)確定，只能先入棧
- 最后一個是左括號的時候，一頂入棧的，此時就會導(dǎo)致棧中不為空，所以顯然匹配失敗
- 最后一個是右括號的時候，可能匹配成功，也可能匹配失敗，這個時候需要看匹配完成之后棧是否為空，如果棧為空，則成功，棧不為空，則失敗。
所以一般我們對一串?dāng)?shù)據(jù)進(jìn)行分析的時候，一般需要考慮的問題，是否為空，常規(guī)情況（中間位置），第一個位置，最后一個位置。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
