棧和隊列一般會是你用來解題的數據結構的一部分。你應該知道如何用鏈表和數組兩種方式來實現它們。 加練兩道題：[利用兩個隊列實現一個棧](http://stackoverflow.com/questions/688276/implement-stack-using-two-queues)，以及[利用兩個棧來實現一個隊列](http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks)。 ### 樹/二叉樹/二叉搜索樹（BST）/字典樹/堆 你可能不會每天都見到樹和圖，但你很可能會在面試時遇到它們，所以你要徹底地看一下這些數據結構。 樹最一般的定義，是和其他結點沒有或者有一個以上關系的結點的集合，但在實踐中，當面試官說“**樹**”的時候，他們指的是一種叫二叉樹的東西。**二叉樹**是一種樹的類型，它的每個結點都至多有兩個子樹，一般被稱為左子樹和右子樹。 你不應該把**二叉樹**和**二叉搜索樹**混淆起來，后者是一種特殊的二叉樹，它的左子樹結點上的值都比父結點小，而右子樹結點上的值都比父結點大或者相等。二叉搜索樹的優點是，如果樹的結構相對平衡（向面試官問清楚這個問題），那么查找、插入和刪除就可以在O(log n)的時間里完成。二叉搜索樹的其他重要屬性，就是你跟著所有的左子樹走，就能得到這個樹上最小的元素，而跟著所有的右子樹走，就能得到這個樹上最大的元素。 請注意，是有辦法讓樹一直保持平衡的，最常用的辦法就是紅黑樹和AVL樹。我不會去弄清楚它具體實現的細節，只要知道有這些數據結構就行。 不過你絕對必須知道遍歷樹（[**tree traversal**](http://en.wikipedia.org/wiki/Tree_traversal)）算法：廣度優先搜索（[**breadth-first-search**](http://en.wikipedia.org/wiki/Breadth-first_search%22%20%5Cl%20%22Pseudocode)）、深度優先搜索（[**depth-first-search**](http://www.jianshu.com/%22http)），以及**中序遍歷**、**后序遍歷**和**前序遍歷**之間的差別。 以下是在Java實現中序遍歷的例子，它可以打印出一個樹的所有值（前序遍歷和后序遍歷幾乎和這個一樣）： ~~~ void inOrderTraversal(Node root) { if (root == null) return; inOrderTraversal(root.getLeft()); // Do something with the value System.out.println(root.getValue()); inOrderTraversal(root.getRight()); } ~~~ 字典樹（[**trie**](http://en.wikipedia.org/wiki/Trie)**，讀****“tree”**）常常被用在字符串問題里，它是一個n元樹，除了根結點以外的每個結點都代表一個字符或者部分或完整的單詞，而且沿著樹的每一條路徑都代表一個單詞。實際上它真的沒有聽起來那么復雜，只要讀一下維基百科上的頁面、了解該如何構建一個字典樹以及如何查詢其中的數值就行。請注意，你可以通過前序遍歷輸出字典樹中的所有鍵。作為一個練習，你可以想一想自己會如何利用字典樹實現自動完成功能。 最后是堆（[**heaps**](http://en.wikipedia.org/wiki/Heap_)），它也被稱為優先隊列，是你應該了解的最后一種數據結構。它們通常都是滿足**堆屬性**的二叉樹：每個結點的子樹的值都比結點本身的值小，或者與它相等。所以根結點的值總是最大的，也就是說你總能找到最大值，但代價就是尋找其他任何一個值所需的時間都是O(n)。插入和刪除所需的時間依然是O(log*n)*。