一、棧：

1、后綴表達式的求值；
2、中綴到后綴表達式的轉換；
3、深度優先搜索的非遞歸實現；
4、動態規劃的優化：用于維護一個凸序列，便于二分查找，如LIS問題的O(nlgn)算法。

二、隊列：
1、樹的層序遍歷；
2、廣度優先搜索；
3、Bellman-Ford算法的SPFA實現；
4、網絡流中FF算法的Edmonds-Karp實現，以及Preflow算法的隊列優化實現。


三、二叉搜索樹：

1、對大量的關鍵字的索引查找；
2、有很多平衡策略以改善其平均性能：
常用平衡樹：AVL，紅黑樹，隨機化BST，Splay Tree，Treap（或叫笛卡兒樹）。

四、散列表（hash表）：
1、一般針對值域較大但狀態很稀疏的應用，比如狀態壓縮記憶化搜索；
2、實現映射功能。

五、檢索樹（Trie）：
1、一般用于字符串索引算法，速度快，但占用空間較大（相對hash）；
2、常用的改進結構：Patricia線索樹，多叉檢索樹（TST）。

六、優先隊列：

1、常用的是二叉堆的實現，具體應用如堆排序和Dijkstra算法；
2、當需要快速合并兩個優先隊列時，常用二項式隊列，實現簡單。
3、注意最大最小堆的配對使用。

七、線段樹和樹狀數組：

1、兩者都可以用于離散對象的統計；
2、后者的步進函數的性質和應用值得注意；
3、前者基本上適用于任何的區間操作，如求區間最值，改變區間的值等。
4、線段樹還可以用于優化狀態的枚舉，經常和動態規劃結合。

八、后綴樹與后綴數組：

1、總體規律是兩者的實現都比較復雜，前者更甚，但是前者的功能也更強大；
2、幾乎可以解決所有常見的關于字符串的算法，如最長回文子串，最長重復子串，以及很多的模式匹配問題。

九、并查集：

1、解決無向圖的連通性問題，如用于Kruskal算法；
2、解決等價關系的查詢（這是它的主要用武之地），如05年Baidu之星初賽的石頭剪子布游戲；
3、優點是實現異常簡單，缺點是合并后無法分離，若需要可以選擇用動態樹。

十、鄰接表和邊表：

1、表示圖的最直接的方法；
2、后者更省空間，并且在一定程度上更好用，比如Bellman-Ford算法。
ps:數組、鏈表太基礎不在考慮之列。