栈/队列

最后更新于:2022-04-01 04:25:54

栈和队列一般会是你用来解题的数据结构的一部分。你应该知道如何用链表和数组两种方式来实现它们。 加练两道题:[利用两个队列实现一个栈](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)*。
';