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