1. 棧和隊(duì)列的概念
1) 棧:只允許一端進(jìn)行插入和刪除的線性表;允許插入和刪除的一端叫做棧頂;不允許插入和刪除的一端叫做棧底.先進(jìn)后出
2) 隊(duì)列:允許插入的一端為隊(duì)首,允許刪除的一端為隊(duì)尾.先進(jìn)先出
2. 存儲(chǔ)結(jié)構(gòu)
1) 棧的順序存儲(chǔ)結(jié)構(gòu):結(jié)構(gòu)體,有數(shù)組和頂指針
2) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):單鏈表
3) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu):結(jié)構(gòu)體,數(shù)組,首尾指針
4) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):單鏈表.
5) 循環(huán)隊(duì)列：隊(duì)列為空時(shí)：rear==front；隊(duì)列滿時(shí)：(rear+1)%maxSize = front.（犧牲了一個(gè)存儲(chǔ)空間單元）
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) 特殊矩陣的壓縮存儲(chǔ)
① 二維數(shù)組對(duì)于二維矩陣對(duì)應(yīng)，數(shù)組的下標(biāo)對(duì)應(yīng)矩陣的下標(biāo)A[m][n];
② 二維矩陣的行優(yōu)先存儲(chǔ)，a[i][j]對(duì)應(yīng)的存儲(chǔ)位置為loc（0，0）+（i*m+j）*L
③ 下三角矩陣行優(yōu)先存儲(chǔ)：a[i,j]在數(shù)組B中的存儲(chǔ)位置為1+2+3+……+i+j
④ 上三角矩陣行優(yōu)先存儲(chǔ)：a[i,j]在數(shù)組B中的存儲(chǔ)位置為n+……+（n+1-i）+j-i；