1. 棧和隊(duì)列的概念
1) 棧:只允許一端進(jìn)行插入和刪除的線性表;允許插入和刪除的一端叫做棧頂;不允許插入和刪除的一端叫做棧底.先進(jìn)后出
2) 隊(duì)列:允許插入的一端為隊(duì)首,允許刪除的一端為隊(duì)尾.先進(jìn)先出
2. 存儲結(jié)構(gòu)
1) 棧的順序存儲結(jié)構(gòu):結(jié)構(gòu)體,有數(shù)組和頂指針
2) 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu):單鏈表
3) 隊(duì)列的順序存儲結(jié)構(gòu):結(jié)構(gòu)體,數(shù)組,首尾指針
4) 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu):單鏈表.
5) 循環(huán)隊(duì)列：隊(duì)列為空時：rear==front；隊(duì)列滿時：(rear+1)%maxSize = front.（犧牲了一個存儲空間單元）
3. 應(yīng)用
1) 棧在表達(dá)式中的應(yīng)用
① 前綴表達(dá)式:(A+B)*C---->*C+AB (波蘭式);(運(yùn)算符在前,從右到左掃描)
② 后綴表達(dá)式:(A+B)*C------>AB+C*.(運(yùn)算符在后，從左到有掃描)
2) 棧遞歸中的應(yīng)用
3) 使用隊(duì)列主要是為了保存下一步的處理步驟
4) 特殊矩陣的壓縮存儲
① 二維數(shù)組對于二維矩陣對應(yīng)，數(shù)組的下標(biāo)對應(yīng)矩陣的下標(biāo)A[m][n];
② 二維矩陣的行優(yōu)先存儲，a[i][j]對應(yīng)的存儲位置為loc（0，0）+（i*m+j）*L
③ 下三角矩陣行優(yōu)先存儲：a[i,j]在數(shù)組B中的存儲位置為1+2+3+……+i+j
④ 上三角矩陣行優(yōu)先存儲：a[i,j]在數(shù)組B中的存儲位置為n+……+（n+1-i）+j-i；