链表，栈，队列
链表（理解与数组的区别）
一种递归的数据结构
结点含有一个（泛型的）元素，和指向后继（前驱）元素引用（单链表 ，循环链表，双链表）
注意点：
有无头结点、最后一个结点指向null
构造链表（头插法，尾插法）
为什么要有栈和队列？
它们是一种数据结构，可以利用它们来解决实际上的问题。并不是说没有它们是不行的，只是有了它们我们可以在计算过程中更加方便，可以大大降低时间复杂度。在递归中我们就会用栈，在键盘输入循环缓冲区问题中会用到队列。
Stack 栈：
栈是一种抽象的数据类型，用户只能从一端插入和删除操作，这一端就是栈顶
后进先出
栈的实现有分两种，一种是数组实现也即是顺序表，一种是链表实现。我个人理解认为链表实现更为方便，因为链表对比顺序表的劣势在栈中是无法体现的，顺序表由于是邻接地址存放，因此在查找上只需要知道下标就能直接查到内容，但是在链表中如果要是查找的话就要遍历，可是在栈中，我们只针对栈顶进行操作，是不会查找某个特定的内容，而若是数组实现栈的话还要考虑栈是否会过界，实时调整栈的大小。
基本操作
1) 创建一个空栈
2) 添加一个元素 push
3) 删除一个元素 pop
4) 判断栈是否为空 IsEmpty
5) 栈中的元素数量 size
6) 取栈S的顶部元素 GetTop
还有许多，诸如IsFull 等操作，这些操作都不难实现，但是如果我们能够自己独立的很轻松实现这些函数，那么我们对栈的概念也一定有所理解了。
在对栈的概念清晰之后就是其的应用了，在算法第四版里就有一个例子，算术表达式求值，也即是Dijkstra双栈算法，是一个栈的典型应用，这是利用的栈的后进先出的特点来对括号进行一一匹配然后进行求值，这也给我们进行了一些启迪，在解决很多实际问题中，可以用双栈法来去求解。具体代码如下
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty()) {
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")")) {
String op = ops.pop();
Double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
这里利用了栈，值得一提的是是对值进行操作时，大家可能会有疑惑为什么值不能直接vals.pop()-vals.pop()呢，那是因为后进的先出，我们输入算术表达式（正常情况），肯定是例如3-1，后输入的是减数，也即是1是减数，但是它是先进栈的也即是先出栈的，因此得先定义了double类型的v，然后把他当作加数减数乘数除数来进行操作，所以代码看上去有些许复杂。
栈与递归调用也有密不可分的关系。一个函数的递归调用过程中势必会用到栈，
Queue 队列：
只允许在表的一端插入元素，而在另一端删除元素。
因此，先进先出。
允许插入的一端称为队尾，允许删除的一端为队头。
基本操作与栈大同小异。
实现队列的基本操作同样对理解队列有重要作用。
