用栈实现队列：
也是用两个栈来实现，包括push栈和pop栈，如下：
遵循的原则：
pop栈为空时，才能将数据导入到pop栈中；
push栈导数据到pop栈时，一次导完。
实现如下：
static class TwoStackQueue { private final Stack<Integer> stackPush; private final Stack<Integer> stackPop; public TwoStackQueue() { stackPush = new Stack<>(); stackPop = new Stack<>(); } // push栈向pop栈导入数据 private void pushToPop() { if (stackPop.isEmpty()) { while (!stackPush.isEmpty()) { stackPop.push(stackPush.pop()); } } } public void add(int num) { stackPush.push(num); pushToPop(); } public int poll() { if (stackPush.isEmpty() && stackPop.isEmpty()) { throw new RuntimeException("Queue is empty!"); } pushToPop(); return stackPop.pop(); } public int peek() { if (stackPush.isEmpty() && stackPop.isEmpty()) { throw new RuntimeException("Queue is empty!"); } pushToPop(); return stackPop.peek(); } }
面试：
一般情况下，图的宽度优先遍历使用的是队列，深度优先遍历使用的是栈；
如果要让用栈实现宽度优先遍历、队列实现深度优先遍历，则需要用两个栈实现队列、两个队列实现栈。
3.递归
怎么从思想上理解递归；
怎么从实际实现的角度出发理解递归。
递归的思想是将一个大的任务分解成小的任务，小的任务再进一步拆解，直到达到某一个边界，最后经过某种逻辑进行整合，得到整个问题的求解。
递归调用时，使用了系统栈，调用的函数放入栈，执行完返回时就会从栈顶pop出；
任何递归都可以改为迭代。
有一类递归的时间复杂度可以确定，时间复杂度原始形式如下：
即条件为：子问题的规模是一致的。
时间复杂度公式如下：
例题：求数组arr[L…R]中的最大值，怎么用递归方法实现。
分析思路：
1)将[L…R]范围分成左右两半。左:[L…Mid]右[Mid+1…R]；
2)左部分求最大值，右部分求最大值；
3)[L…R]范围上的最大值，是max{左部分最大值，右部分最大值}。
注意:2）是个递归过程，当范围上只有一个数，就可以不用再递归了。
思路如下：
这里的子问题规模是原问题的一半，所以可以求出时间复杂度，时间复杂度如下：
实现如下：
public class MaxWithRecursion { public static int getMax(int[] arr) { return process(arr, 0, arr.length - 1); } // arr[L..R]范围上求最大值 public static int process(int[] arr, int L, int R) { // arr[L..R]范围上只有1个数，直接返回 if (L == R) { return arr[L]; } int mid = L + ((R - L) >> 1); // 中点 int leftMax = process(arr, L, mid); int rightMax = process(arr, mid + 1, R); return Math.max(leftMax, rightMax); } }
4.哈希表和有序表
哈希表
1)哈希表在使用层面上可以理解为—种集合结构；
2)如果只有key、没有伴随数据value，可以使用HashSet结构；
3)如果既有key，又有伴随数据value，可以使用HashMap结构；
4)有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事；
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大；
6)放入哈希表的元素，如果是基础类型，内部按值传递，内存占用是这个元素的大小；
7)放入哈希表的元素，如果不是基础类型（是自定义类型），内部按引用传递，内存占用是8字节（也就是引用地址的大小）。
使用如下：
static class Node { public int value; public LinkedList.Node next; public Node(int data) { value = data; } } public static void testHashMap() { // 键值对 HashMap<Integer, String> map = new HashMap<>(); // 新增 map.put(1, "one"); map.put(2, "two"); map.put(3, "three"); map.put(4, "four"); map.put(5, "five"); System.out.println(map.containsKey(1)); System.out.println(map.containsKey(10)); System.out.println(map.containsValue("one")); System.out.println(map.containsValue("one")); System.out.println(map.get(1)); System.out.println(map.get(10)); // 修改 map.put(1, "一"); System.out.println(map.get(1)); map.remove(5); System.out.println(map.get(5)); System.out.println("--------------------"); // 集合元素 HashSet<String> set = new HashSet<>(); set.add("one"); System.out.println(set.contains("one")); set.remove("one"); System.out.println(set.contains("one")); System.out.println("--------------------"); // 引用传递和值传递 int a = 10000000; int b = 10000000; System.out.println(a == b); // int属于基本数据类型，使用值传递，所以比较时只比较值，不比较地址 Integer c = 10000000; Integer d = 10000000; System.out.println(c == d); // Integer属于引用数据类型，使用引用传递，所以比较时比较地址，不比较值，要比较值使用equals方法 System.out.println(c.equals(d)); Integer e = 128; Integer f = 128; System.out.println(e == f); e = 127; f = 127; System.out.println(e == f); // -128到127之间，使用常量池，转化为值传递，不在这个区间才使用引用传递 // 新增 map.put(10000, "10000"); System.out.println(map.get(10000)); // 修改 map.put(10000, "一万"); System.out.println(map.get(10000)); // 放入哈希表的元素，如果是基础类型，内部按值传递 HashMap<Node, String> map2 = new HashMap<>(); Node node1 = new Node(1); Node node2 = new Node(1); map2.put(node1, "node1"); map2.put(node2, "node1 too"); System.out.println(map2.get(node1)); System.out.println(map2.get(node2)); node2 = node1; System.out.println(map2.get(node2)); }
输出：
true false true true one null 一 null -------------------- true false -------------------- true false true false true 10000 一万 node1 node1 too node1
有序表：
有序表指集合内的元素按照某种规则进行排序；
使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，时间复杂度为O(logN)。
AVL、SB树、红黑树和跳表都可以实现有序表，通过调整实现平衡。
使用有序表TreeMap如下：
public static void testTreeMap() { TreeMap<Integer, String> map = new TreeMap<>(); map.put(3, "three"); map.put(7, "seven"); map.put(2, "two"); map.put(1, "one"); map.put(5, "five"); map.put(9, "nine"); map.put(6, "six"); System.out.println(map.containsKey(1)); System.out.println(map.containsKey(10)); System.out.println(map.get(1)); System.out.println(map.get(10)); // 修改 map.put(5, "五"); System.out.println(map.get(5)); // 删除 map.remove(5); System.out.println(map.get(5)); // 查看顺序 System.out.println(map.firstKey()); System.out.println(map.lastKey()); System.out.println(map); // 小于等于5的最近的值 System.out.println(map.floorKey(5)); // 大于等于5的最近的值 System.out.println(map.ceilingKey(5)); }
输出：
true false one null 五 null 1 9 {1=one, 2=two, 3=three, 6=six, 7=seven, 9=nine} 3 6
总结
有很多常用的数据结构，每种数据结构都有适用的场景，可以根据自己的需要进行选择。
