8.3
和链表问题一样，熟练掌握数据结构的基本原理，栈与队列问题处理起来要容易得多。当然，有些问题也可能相当棘手。部分问题不过是对基本数据结构略作调整，而其他问题则要难得多。实现一个栈栈采用后进先出（LIFO）顺序。换言之，像一堆盘子那样，最后入栈的元素最先出栈。
下面给出了栈的简单实现代码。注意，栈也可以用链表实现。实际上，栈和链表本质上是一样的，只不过用户通常只能看到栈顶元素。
classStack{
Nodetop;
Objectpop(){
if(top！=null){
Objectitem=top.data;
top=top.next;
returnitem;}
returnnull;}
voidpush(Objectitem){
Nodet=newNode(item);
t.next=top;
top=t;}
Objectpeek(){
returntop.data;}}
实现一个队列队列采用先进先出（FIFO）顺序。就像一支排队购票的队伍那样，最早入列的元素也是最先出列的。队列也可以用链表实现，新增元素追加至表尾。
classQueue{
Nodefirst,last;
voidenqueue(Objectitem){
if(first==null){
last=newNode(item);
first=last;
}else{
last.next=newNode(item);
last=last.next;}}
Objectdequeue(){
if(first！=null){
Objectitem=first.data;
first=first.next;18returnitem;}returnnull;}
}
面试题目
3.1描述如何只用一个数组来实现三个栈。
3.2请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)。
3.3设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
进阶实现一个popAt(intindex)方法，根据指定的子栈，执行pop操作。
3.4在经典问题汉诺塔中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制：每次只能移动一个盘子；盘子只能从柱子顶端滑出移到下一根柱子；盘子只能叠在比它大的盘子上。请运用栈，编写程序将所有盘子从第一根柱子移到最后一根柱子。
3.5实现一个MyQueue类，该类用两个栈来实现一个队列。
3.6编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。
3.7有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（根据进入收容所的时间长短）的动物，或者，可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat等。允许使用Java内置的LinkedList数据结构。
8.4
许多求职者会觉得树与图的问题是最难对付的。检索这两种数据结构比数组或链表等线性数据结构要复杂得多。此外，在最坏情况和平均情况下，检索用时可能差别巨大，对于任意算法，我们都要从这两方面进行评估。能够自如地从无到有实现树或图对求职者而言非常重要。需要注意的潜在问题树与图的问题容易出现含糊的细节和错误的假设。务必留意下列问题，必要时寻求澄清。
二叉树与二叉查找树碰到二叉树问题时，许多求职者会假定面试官问的是二叉查找树。此时务必问清楚二叉树是否为二叉查找树。二叉查找树附加有如下条件：对于任意结点，左子结点小于或等于当前结点，后者又小于所有右子结点。平衡与不平衡许多树都是平衡的，但并非全都如此。树是否平衡要找面试官确认。如果树是不平衡的，你应当从平均情况和最坏情况所需时间来描述自己的算法。注意，树的平衡有多种方法，平衡一棵树只意味着子树的深度差不会超过一定值，并不表示左子树和右子树的深度完全相同。
完满和完整（FullandComplete）完满和完整树的所有叶结点都在树的底部，所有非叶结点都有两个子结点。注意完满和完整树极其稀少，因为一棵树必须正好有2n-1个结点才能满足这个条件。二叉树遍历面试之前，你应该能够熟练实现中序、后序和前序遍历。其中最常见的是中序遍历，先遍历左子树，然后访问当前结点，最后遍历右子树。
树的平衡：红黑树和平衡二叉树学习如何实现平衡树可助你成为更好的软件工程师，只不过面试中很少会问及平衡树。你应该熟悉平衡树各种操作的执行时间，大致了解如何平衡一棵树。当然，就面试而言，掌握个中细节也许没什么必要。单词查找树（trie）trie树是n层树的一种变体，其中每个结点存储有字符。整棵树的每条路径自上而下表示一个单词。一棵简单的trie树类似下图：
图的遍历大部分求职者都比较熟悉二叉树的遍历，但图的遍历则要难得多。广度优先搜索（BFS）更是难上加难。值得注意的是，广度优先搜索（BFS）和深度优先搜索（DFS）通常用于不同的场景。如要访问图中所有结点1，或者访问最少的结点直至找到想找的结点，DFS一般最为简单。不过，如果一棵树的规模非常大，在离最初结点太远时想要随时退出的话，DFS可能会有问题；我们可能搜索了该结点的成千上万个祖先结点，却还未搜索该结点的全部子结点。对于这些情况，一般首选BFS。1图中的“结点”一般称为顶点，这里依原文译作结点。——译者注
深度优先搜索（DFS）在DFS中，我们会访问结点r，然后循环访问r的每个相邻结点。在访问r的相邻结点n时，我们会在继续访问r的其他相邻结点之前先访问n的所有相邻结点。也就是说，在继续搜索r的其他子结点之前，我们会先穷尽搜索n的子结点。注意，前序和树遍历的其他形式都是一种DFS。主要区别在于，对图实现该算法时，我们必须先检查该结点是否已访问。如果不这么做，就可能陷入无限循环。下面是实现DFS的伪代码。
voidsearch(Noderoot){
if(root==null)return;
visit(root);
root.visited=true;
foreach(Nodeninroot.adjacent){
if(n.visited==false){
search(n);}}}
广度优先搜索（BFS）BFS相对不太直观，除非之前熟悉BFS的实现，否则大部分求职者都会觉得它很难对付。在BFS中，我们会在搜索r的“孙子结点”之前先访问结点r的所有相邻结点。用队列实现的迭代方案往往最有效。
voidsearch(Noderoot){
Queuequeue=newQueue();
root.visited=true;
visit(root);
queue.enqueue(root);//加至队列尾部
while(!queue.isEmpty()){
Noder=queue.dequeue();//从队列头部移除
foreach(Nodeninr.adjacent){
if(n.visited==false){
visit(n);
n.visited=true;
queue.enqueue(n);}}}}
当面试官要求你实现BFS时，切记关键在于队列的使用。用了队列，这个算法的其余部分自然也就成型了。
面试题目
4.1实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个结点，其两棵子树的高度差不超过1。
4.2给定有向图，设计一个算法，找出两个结点之间是否存在一条路径。
4.3给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉查找树。
4.4给定一棵二叉树，设计一个算法，创建含有某一深度上所有结点的链表（比如，若一棵树的深度为D，则会创建出D个链表）。
4.5实现一个函数，检查一棵二叉树是否为二叉查找树。
4.6设计一个算法，找出二叉查找树中指定结点的“下一个”结点（也即中序后继）。可以假定每个结点都含有指向父结点的连接。
4.7设计并实现一个算法，找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。注意：这不一定是二叉查找树。
4.8你有两棵非常大的二叉树：T1，有几百万个结点；T2，有几百个结点。设计一个算法，判断T2是否为T1的子树。如果T1有这么一个结点n，其子树与T2一模一样，则T2为T1的子树。也就是说，从结点n处把树砍断，得到的树与T2完全相同。
给定一棵二叉树，其中每个结点都含有一个数值。设计一个算法，打印结点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根结点或叶结点开始或结束。