一、棧
1.1 棧的定義
- 棧（Stack）：只允許在一端進行插入或刪除操作的線性表棉安。首先棧是一種線性表，但是限定這種線性表只能在某一端進行插入和刪除操作。
- 棧頂（Top）：線性表允許進行插入和刪除的那一端绒净。
- 棧底（Bottom）:固定的，不允許進行插入和刪除的另一端偿衰。
- 空棧：不含任何元素的空表挂疆。
1.2 棧的基本操作
- InitStack(&S)：初始化一個空棧 S。
- StackEmpty(S)：判斷一個棧是否為空下翎，若棧 S 為空返回 true缤言，否則返回 false。
- Push(&S视事，x)：進棧胆萧，若棧 S 未滿，將 x 加入使之成為新棧頂俐东。
- Pop(&S跌穗，&x)：出棧，若棧 S 非空虏辫，彈出棧頂元素蚌吸，并用 x 返回。
- GetTop(S砌庄，&x)：讀棧頂元素羹唠，若棧頂元素為空，用 x 返回棧頂元素鹤耍。
- ClearStack(&S)：銷毀棧肉迫，并釋放棧 S 占用的存儲空間。
1.3 棧的順序存儲結(jié)構(gòu)
- 順序棧的實現(xiàn)：棧的順序存儲稱為順序棧稿黄，是利用一組地址連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素喊衫，同時附設(shè)一個指針（Top）指示當(dāng)前棧頂?shù)奈恢谩?/li>
- 順序棧的基本運算：初始化、判椄伺拢空族购、進棧壳贪、出棧、讀棧頂元素寝杖。
- 共享棧：利用棧底位置相對不變的特性违施，可以讓兩個順序棧共享一個一維數(shù)據(jù)空間，將兩個棧的棧底分別設(shè)置在共享空間的兩端瑟幕，兩個棧頂向共享空間的中間延申磕蒲。
1.4 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)
- 采用鏈?zhǔn)酱鎯Φ臈３蔀殒湕＃湕５膬?yōu)點是便于多個棧共享存儲空間和提高其效率只盹，且不存在棧滿上溢的情況辣往。
- 通常采用單鏈表實現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進行殖卑。
- 采用鏈?zhǔn)酱鎯φ鞠鳎阌诮Y(jié)點的插入與刪除。
二孵稽、隊列
2.1 隊列的定義
- 隊列簡稱隊许起，是一種操作受限的線性表，只允許在表的一端進行插入菩鲜，而在表的另一端進行刪除园细。向隊列中插入元素稱為入隊或進隊；刪除元素稱為出隊或離隊睦袖。
- 操作特性為先進先出珊肃，又被稱為先進先出的線性表荣刑。
- 隊頭（Front）：允許刪除的一端馅笙，又稱為隊首。
- 隊尾（Rear）：允許插入的一端厉亏。
- 空隊列：不含任何元素的空表董习。
2.2 隊列的順序存儲結(jié)構(gòu)
- 隊列的順序存儲：隊列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲單元存放隊列中的元素，并附設(shè)兩個指針 front 和 rear 分別指示隊頭元素和隊尾元素的位置爱只。
- 初始條件（對空條件）：Q.front == Q.rear == 0;
- 進隊操作：隊不滿時皿淋，先送值到隊尾元素，再送隊尾指針加 1恬试。
- 出隊操作：隊不空時窝趣，先取隊頭元素值，再將隊頭指針加 1训柴。
- 隊空條件為：Q.rear == MaxSize ;
2.3 循環(huán)隊列
- 把存儲隊列元素的表從邏輯上看成一個環(huán)哑舒，當(dāng)隊首指針 Q.front = MaxSize-1后，再前進一個位置就自動到 0幻馁，可利用除法取余（%）來實現(xiàn)洗鸵。
- 初始時：Q.front = Q.rear = 0;
- 隊首指針進 1：Q.front = (Q.front+1)%MaxSize越锈；
- 隊尾指針進 1：Q.rear = (Q.rear+1)%MaxSize；
- 隊列長度：(Q.rear+MaxSize-Q.front)%MaxSize膘滨；
- 出隊入隊時：指針都按順時針方向進 1甘凭；
- 犧牲一個單元來區(qū)分隊空和隊滿，入隊少用一個隊列單元火邓，即隊頭指針在隊尾指針的下一個位置作為隊滿的標(biāo)志丹弱。
- 隊滿條件為：(Q.rear+1)%MaxSize==Q.front。
- 隊空條件為：Q.front == Q.rear铲咨。
- 隊中元素的個數(shù)：(Q.rear-Q.front+MaxSize)%MaxSize
- 類型中增設(shè)表示元素個數(shù)的數(shù)據(jù)成員
- 隊空：Q.size = 0;
- 隊滿：Q.size = MaxSize;
- 上述兩種情況均有Q.front = Q.rear
- 類型中增設(shè) tag 數(shù)據(jù)成員蹈矮，以區(qū)分是隊空還是隊滿。
- tag 等于零的情況下鸣驱，若因刪除導(dǎo)致Q.front == Q.rear 則為隊空泛鸟；
- tag 等于 1 的情況下，若因插入導(dǎo)致Q.front == Q.rear 則為隊滿踊东；
- 循環(huán)隊列的操作：初始化北滥，判隊空，入隊闸翅，出隊
2.4 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)
- 隊列的鏈?zhǔn)奖硎痉Q為鏈隊列再芋，是一個同時帶有隊頭指針和隊尾指針的單鏈表。
- 頭指針指向頭節(jié)點坚冀，尾指針指向尾結(jié)點济赎，即鏈表的最后一個結(jié)點。
- 當(dāng) Q.front == NULL记某，且 Q.rear == NULL 時司训，鏈表隊列為空。
- 出隊時液南，首先判斷隊是否為空壳猜，若不空，則取出隊頭元素滑凉，將其從鏈表中摘除统扳，并讓 Q.front 指向下一個結(jié)點（若該節(jié)點為最后一個節(jié)點，則置 Q.front 和 Q.rear 都為NULL）畅姊。
- 入隊時咒钟，建立一個新節(jié)點，將新節(jié)點插入到鏈表的尾部若未，并改讓 Q.rear 指向這個新插入的結(jié)點（若原隊列為空隊朱嘴，則令 Q.front 也指向該節(jié)點。
- 用單鏈表表示的鏈?zhǔn)疥犃刑貏e適合于數(shù)據(jù)元素變動比較大的情形陨瘩，而且不存在隊列滿且產(chǎn)生溢出的問題腕够。
- 假如程序中要使用多個隊列级乍，于多個棧的情況一樣，最好使用鏈?zhǔn)疥犃兄阆妫@樣就不會出現(xiàn)存儲分配不合理和溢出的問題玫荣。
- 鏈?zhǔn)疥犃械幕静僮鳎撼跏蓟嘘牽沾笾睿腙犕背В鲫?/li>
2.5 雙端隊列
- 雙端隊列是指允許兩端都可以進行入隊和出隊操作大的隊列，其元素的邏輯結(jié)構(gòu)仍是線性资柔，將隊列的兩端分別稱為前端和后端焙贷，兩邊都可以入隊和出隊。
- 在雙端隊列進隊時：前端進的元素排列在隊列中后端進的元素后面贿堰，后端進的元素排列在隊列中前端元素進的元素的后面辙芍。
- 在雙端隊列出隊時：無論前端還是后端出隊，先出的元素排在后出的元素前面羹与。
- 輸出受限的雙端隊列：允許在一端進行插入和刪除故硅，但在另一端只允許插入的雙端隊列稱為輸出受限的雙端隊列。
- 輸入受限的雙端隊列：允許在一端進行插入和刪除纵搁，但在另一端只允許刪除的雙端隊列稱為輸入受限的雙端隊列吃衅。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則該雙端隊列就蛻變?yōu)閮蓚€棧底相鄰接的棧了腾誉。
三徘层、棧和隊列的應(yīng)用
- 棧在括號匹配中的應(yīng)用
- 棧在表達式求值中的應(yīng)用
- 棧在遞歸中的應(yīng)用
- 隊列在層次遍歷中的應(yīng)用
- 隊列在計算機系統(tǒng)中的應(yīng)用
四、特殊矩陣的壓縮存儲
- 矩陣在計算機圖形學(xué)利职、工程計算中占有舉足輕重的地位趣效，在數(shù)據(jù)結(jié)構(gòu)中考慮的是如何用最小的內(nèi)存空間來存儲同樣的一組數(shù)據(jù)。
4.1 數(shù)組
- 數(shù)組和線性表的關(guān)系：數(shù)組是線性表的推廣眼耀。一維數(shù)組可以看作是一個線性表英支，二維數(shù)組可以看作元素是線性表的線性表，以此類推哮伟。
- 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變妄帘，因此楞黄，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組就只會有存取元素和修改元素的操作抡驼。
4.2 數(shù)組的存儲結(jié)構(gòu)
- 一個數(shù)組的所有元素在內(nèi)存中占用一端連續(xù)的存儲空間鬼廓。
- 對于多維數(shù)組，有兩種映射方法 ：按行優(yōu)先和按列優(yōu)先致盟。
- 按行優(yōu)先：先行后列碎税，先存儲行號較小的元素尤慰，行號相等先存儲列號較小的元素。
- 按列優(yōu)先：先列后行雷蹂。
4.3 矩陣的壓縮存儲
- 壓縮存儲：指為多個值相同的元素只分配一個存儲空間伟端，對零元素不分配存儲空間，其目的是為了節(jié)省存儲空間匪煌。
- 特殊存儲：指具有許多相同矩陣元素或零元素责蝠，并且這些相同矩陣元素或零元素的分布有一定規(guī)律性的矩陣。常見的特殊矩陣有對稱矩陣萎庭、上（下）三角矩陣霜医、對角矩陣等。
- 特殊矩陣的壓縮存儲方法：找出特殊矩陣中值相同的矩陣元素的分布規(guī)律驳规，把那些呈現(xiàn)規(guī)律性分布的值相同的多個矩陣元素壓縮存儲到一個存儲空間中肴敛。
4.4 稀疏矩陣
- 矩陣元素個數(shù) s 相對于矩陣中非零元素個數(shù) t 來說非常多，即 s >> t 為的矩陣稱為稀疏矩陣吗购。
- 將非零元素及其相應(yīng)的行和列構(gòu)成一個三元組（行標(biāo)值朋，列標(biāo)，值）巩搏，然后按照某種規(guī)律存儲這些三元組昨登。
- 稀疏矩陣壓縮存儲后便失去了隨機存取的特性。
