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；