四、栈
1. 什么是栈？
栈就类似于水桶，只有水桶口一个开口，用水桶装水的时候，最先装到的水在桶底，而用水桶中的水的时候，最先用的是最后装的在最上面的水。栈也是这样，只允许在栈顶操作，元素有后进先出(last in first out，简称LIFO)的特点，添加元素叫入栈，删除元素叫出栈。
2. 栈的应用：
- 撤销功能：我们都知道像word记事本等编辑器的撤销功能，其实就是使用栈来实现的。你的操作都会记录在栈中，当你撤销的时候，你最后的操作就会出栈，就恢复到之前的状态。
- 程序调用的系统栈：比如有三个方法A、B、C，A方法执行到第三行调用了B，B执行到第四行调用了C，那么当C执行完后，从哪里开始执行呢？其实当执行A方法转而去执行B方法的时候，系统栈就会记录这个位置，比如这个位置叫A3，执行B方法转而去执行C方法的时候，也会记录这个位置，比如叫B4，那么现在系统栈中自顶向下为B4、A3。当执行完C后，发现系统栈中栈顶元素为B4，那么计算机就知道接下来就从B方法的第四行开始执行了。
- 括号匹配问题：一般的编辑器都会检查你输入的括号是否有效，'(' 以 ')'闭合时为有效，'(' 以 '}' 闭合是为无效。这就是用栈来实现检查这个功能的。
3. 栈的实现：
栈可以基于数组实现，也可以使用链表实现。先看看基于数组如何实现。
- 首先创建一个Stack接口，提供对栈的一些操作的方法。
public interface Stack<E> { /** 获取栈中元素个数 */ int getSize(); /** 栈是否为空 */ boolean isEmpty(); /** 添加元素 */ void push(E e); /** 删除元素 */ E pop(); /** 获取栈顶元素 */ E peek(); }
- 基于数组(自己封装的数组)实现栈。
public class ArrayStack<E> implements Stack<E> { Array<E> array;//自己封装的动态数组 /** 构造方法，初始化栈 */ public ArrayStack(int capacity){ array = new Array<>(capacity); } public ArrayStack(){ array = new Array<>(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public void push(E e) { array.addLast(e);//因为只能在栈顶添加，所以是addLast } @Override public E pop() { return array.removeLast();//因为只能在栈顶删除，所以是removeLast } @Override public E peek() { return array.getLast();//数组的最后一个就是栈顶元素 } public int getCapacity(){ return array.getCapacity(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Stack:"); res.append("["); for (int i = 0;i<array.getSize();i++){ res.append(array.get(i)); if (i != array.getSize() - 1){ res.append(", "); } } res.append("] top"); return res.toString(); } }
- 基于链表(自己实现的链表)实现栈：
public class LinkedListStack<E> implements Stack<E> { private MyLinkedList<E> list;//自己实现的链表 public LinkedListStack(){ list = new MyLinkedList<>(); } @Override public int getSize() { return list.getSize(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void push(E e) { list.addFirst(e); } @Override public E pop() { return list.removeFirst(); } @Override public E peek() { return list.getFirst(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Stack: top"); res.append(list); return res.toString(); } }
上面分别基于数组和链表实现了栈的一些基本操作。为了操作的方便，基于数组的时候，数组末尾是栈顶，基于链表的时候，链表头是栈顶。java.util包中也有一个Stack类，就是java提供的实现好了的栈，它提供的方法也和上面的差不多。
- 栈的应用例子(括号匹配问题)：
问题描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
public boolean isValid(String s){ Stack<Character> stack = new Stack<>(); for (int i=0;i<s.length();i++){ char c = s.charAt(i); if (c == '(' || c == '[' || c == '{'){ stack.push(c);//把左括号压入栈中 }else { if (stack.isEmpty()){ return false; } char topChar = stack.pop(); if (c == ')' && topChar != '('){ return false; } if (c == ']' && topChar != '['){ return false; } if (c == '}' && topChar != '{'){ return false; } } } return stack.isEmpty(); }
小结：栈也是线性结构的，只允许在栈顶操作，添加元素叫入栈，删除元素叫出栈，元素有先进后出的特点。
五、队列
1. 什么是队列？
队列也是一种线性结构，它只能从队尾添加元素，从队首取出元素，是一种先进先出(first in first out，简称FIFO)的数据结构。就跟生活当中的排队是一样的，要排队只能从队尾加入，从队首离开。
2. 队列的实现：
- 首先创建一个Queue接口，提供操作队列的一些方法。
public interface Queue<E> { /** 获取队列中元素的个数 */ int getSize(); /** 判断队列是否为空 */ boolean isEmpty(); /** 入队 */ void enqueue(E e); /** 出队 */ E dequeue(); /** 获取队首元素 */ E getFront(); }
- 基于数组(自己实现的动态数组)实现队列：
public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(int capacity){ array = new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @Override public void enqueue(E e) { array.addLast(e); } @Override public E dequeue() { return array.removeFirst(); } @Override public E getFront() { return array.getFirst(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue:"); res.append("front ["); for (int i = 0;i<array.getSize();i++){ res.append(array.get(i)); if (i != array.getSize() - 1){ res.append(", "); } } res.append("] tail"); return res.toString(); } }
- 基于链表(自己实现链表)实现队列：
public class LinkedListQueue<E> implements Queue<E> { private class Node { public E e;//存放的元素 public Node next;//下一个节点 public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head,tail;//头节点和尾节点 private int size;//元素个数 public LinkedListQueue(){ head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** 入队，在链表的尾部进行操作 */ @Override public void enqueue(E e) { if (tail == null){ tail = new Node(e); head = tail; }else { tail.next = new Node(e); tail = tail.next; } size ++; } /** 出队，在链表头操纵 */ @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("队列为空"); } Node delNode = head; head = head.next; delNode.next = null; if (head == null){ tail = null; } size --; return delNode.e; } @Override public E getFront() { if (isEmpty()){ throw new IllegalArgumentException("队列为空"); } return head.e; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("queue:front "); Node cur = head; while (cur != null){ res.append(cur + "--> "); cur = cur.next; } res.append("NULL tail"); return res.toString(); } }
基于链表的队列并没有直接使用上面第三部分实现的链表，而是重新写了一下，把虚拟头节点去掉了，同时多维护了一个尾节点tail。这样一来，入队操作在链表尾部进行，出队操作在链表头部进行，时间复杂度都是O(1)，如果不维护一个尾节点，那么入队和出队总有一个时间复杂度是O(n)。基于数组的队列出队这个操作，出队是删除队首元素，对应的底层数组的操作就是删除数组中第一个元素，删除第一个元素的话，那么其他元素都得往前移一位，所以这个时间复杂度是O(n)的。因此就出现了循环队列。
3. 循环队列：
- 循环队列分析：
上面说到了，出队的时候会导致底层数组第二个元素开始都前移一位，这样性能不是很好。循环队列就是用front来记录队首的位置，tail指向队尾元素的后一个位置。一开始数组为空时，front和tail同时指向底层数组的0索引处，即
front == tail //队列为空
当有元素入队时，tail++即可，当0索引处的元素出队后，front++即可，后面的元素不用前移，这样就性能就提升了。
在上图删除元素的基础上继续添加元素，当索引为4处也存放有元素了，此时tail指向索引5，那么tail++就超出索引范围了，若要往索引5处添加元素，此时tail应该指向0才对，这才是循环队列。
如果要让tail指向5后再指向0，其实tail++是不能实现的，应该是
tail = (当前索引 + 1) % 数组长度
在上图，tail指向的0索引处是没有元素的，如果此时再往0索引处添加元素，那么tail就等于1，又和front相等了。上面说了，front 等于 tail的时候是队列为空，现在队列满又是这种情况，所以不行。因此规定：
tail + 1 == front //队列已满
所以循环队列是浪费了数组的一个空间的。
- 编码实现循环队列：
同样实现Queue接口。
public class LoopQueue<E> implements Queue<E> { private E[] data;//存放元素的数组 private int front,tail;//队首和队尾 private int size;//队列中元素个数 public LoopQueue(int capacity){ data = (E[]) new Object[capacity+1]; front = 0; tail = 0; size = 0; } public LoopQueue(){ this(10); } /** 获取队列容积(数组长度 - 1 ) */ public int getCapacity(){ return data.length - 1; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } @Override public void enqueue(E e) { if ((tail + 1)% data.length == front){//队列已满 resize(getCapacity() * 2);//给数组扩容 } data[tail] = e; tail = (tail + 1) % data.length; size ++; } /** 给数组扩容 */ private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity + 1]; for (int i=0;i<size;i++){ newData[i] = data[(i + front) % data.length]; } data = newData; front = 0; tail = size; } @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("空队列不能执行出队操作"); } E e = data[front]; data[front] = null; front = (front + 1) % data.length; size --; if (size == getCapacity() / 4 && getCapacity() /2 != 0){ resize(getCapacity() / 2);//缩容 } return e; } @Override public E getFront() { if (isEmpty()){ throw new IllegalArgumentException("队列为空"); } return data[front]; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("loopQueue: size = %d,capacity = %d\n",size,getCapacity())); res.append("front:["); for (int i = front;i != tail ; i=(i+1)%data.length){ res.append(data[i]); if ((i+1) % data.length != tail){ res.append(", "); } } res.append("] tail"); return res.toString(); } }
小结：队列也是线性结构的，跟生活中的排队是一样的，在队首删除元素，队尾添加元素，有先进先出的特点。
六、递归
本文本来是讲数据结构，但这里先说说递归，因为接下来的几种数据结构都有用到递归算法。
1. 什么是递归？
递归，就是方法里面调用方法自身。我们直到方法里面也可以调用其他的方法，调用其他方法也很容易理解，其实方法里面也可以调用方法本身，如下：
public void fun(){ fun(); }
但是上面这段代码运行一段时间后会报错，因为这个递归没有结束条件，会形成死循环，一直往栈中压入fun方法，最后导致栈内存溢出。所以递归一定要有结束条件。还要注意，如果递归太深了，即使有结束条件，也可能会出现栈内存溢出错误。
2. 递归的使用：
需求：求1到n的和。
- 分析：
/** 使用递归求1到n的和 */ public int sum(int n){ }
假设现在传入的n等于4，那么就是求1到4的和。1到4的和就可以写出如下形式：
4 + 3 + 2 + 1 //sum(4) 求1到4的和
4后面的 3 + 2 + 1 又可以看成是求1到3的和，因此可以写成：
4 + sum(3)
sum(3) 其实又可以写成 3 + sum(2) ，因此整体又变成：
4 + 3 + sum(2)
sum(2) 又可以写成 2 + sum(1)，因此又变成：
4 + 3 + 2 + sum(1)
写到这里，我们发现了规律，其实求1到n的和，就可以写成 n + sum(n-1) 。那么结束条件是什么呢？通过上面的分析可知，因为 sum(1) 就是等于1，所以结束条件就是当 n等于1 的时候，直接返回一个 1 就行了。
- 递归实现1到n的求和：
/** 使用递归求1到n的和 */ public int sum(int n){ if (n == 1){ return 1; } return n + sum(n-1); }
上面分析了一下如何使用递归求1到n的和，并且给出了实现。下面就来看一下这段求和代码具体的执行过程：
首先看红线的执行流程，图一中，传进去的n是4，执行到第四行时，变成了4 + sum(3)，接着就跳到了图二，传进去的n为3，执行到第四行，就变成了3 + sum(2)，再次调用sum方法，到了图三，传进去的n是2，执行到第四行，变成了2 + sum(1），最后到了图四，传进去的n是1，执行到第三行，返回一个1；这个时候看黄线的执行流程，这个1就是图三的sum(1)的执行结果，把这个1回传到图三中，所以图三中返回的res就是 2 + 1 ，图三return的 2 + 1 再传给图二，结果图二return的就是 3 + 2 + 1，这个结果再传给图一，最后return的就是 4 + 3 + 2 + 1。
总结：
为避免篇幅过长，本文就先聊到这。本文主要说了一下数组、链表、栈和队列这四种线性结构。数组和链表是最基本的数据结构，可以辅助实现其他数据结构，像栈和队列，既可以用数组实现，也可以用链表实现。用数组实现的叫顺序存储，用链表实现的叫链式存储。最后还说了一下递归，为接下来的学习做准备。
