栈
栈（Stack）的基本性质是先进后出（LIFO）
1 栈的实现
从上图中可以分析，栈的基本操作有：入栈、出栈
定义我们要实现的栈的API：
public class Stack<Item> {
Stack(); //构造函数
void push(Item item); //添加一个元素
Item pop(); //删除最近添加的元素
boolean isEmpty(); //栈是否为空
int size(); //栈中的元素数量
}
1.1 数组实现栈
public class ArrayStack<Item> implements Iterable<Item> {
//private Item[] a = new Item[2]; 创建泛型数组在Java中是不允许的
private Item[] a = (Item[]) new Object[1];
private int size = 0;
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void push(Item item) {
//扩容
if (size == a.length) {
resize(2 * a.length);
}
a[size++] = item;
}
private void resize(int max) {
//将栈移动到一个大小为max的新数组
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < size; i++) {
temp[i] = a[i];
}
a = temp;
}
private Item pop() {
//缩容
Item item = a[--size];
a[size] = null;
if (size > 0 && size == a.length / 4) {
resize(a.length / 4); //避免频繁执行扩容、缩容操作
}
return item;
}
@Override
public Iterator<Item> iterator() {
return new ArrayIterator();
}
private class ArrayIterator implements Iterator<Item> {
private int i = size;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
@Override
public void remove() {
}
}
1.泛型的使用；
2.数组的扩容、缩容；
3.迭代器的实现。
1.2 链表实现栈
public class ListStack<Item> implements Iterable<Item> {
private Node first;
private int size;
public boolean isEmpty() {
return first == null;
}
public int size() {
return size;
}
public void push(Item item) {
Node oldFirst = first;
first = new Node(item);
first.next = oldFirst;
size++;
}
private Item pop() {
Item item = first.item;
first = first.next;
size--;
return item;
}
class Node {
Item item;
Node next;
public Node(Item item) {
this.item = item;
}
}
@Override
public Iterator iterator() {
return new MyListIterator();
}
class MyListIterator implements Iterator<Item> {
int i = size;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
Item item = first.item;
first = first.next;
return item;
}
}
}
2 习题演练
2.1 最小栈（leetcode-155）
考察对栈的基本性质的理解和栈的运用。
2.2 用栈实现队列（leetcode-232）
考察对栈和队列的基本性质的理解，以及它们之间的转换。
准备两个栈，一个用于装入栈的元素（记为栈1），一个用于出栈（记为栈2）。元素以FILO的方式进栈1，再以FILO的方式进另一个栈2，，然后再从栈2出栈，就可以将“先进后出”变为“先进先出”。
注意两点：
- 栈1将元素倒入栈2时，必须是将所有元素全部倒入；
- 只有在栈2为空时，才需要将栈1的元素倒入栈2.
2.3 实现栈的逆序
例如栈中元素由上到下依次为（1,2,3），要求将元素顺序变为（3,2,1），不能使用额外的数据结构，只能用该栈本身的操作来实现。
考察栈的基本性质和递归思想。
思路：分为两步，每一步都需要用递归。
- 获取栈最底部的元素并移除。如（1,2,3）获取到3,并移除3，栈变为（1,2）；
- 将1获取到的元素压入栈中，注意：先获取到的后插入（是不是很像栈的先进后出？栈与递归具有相通性，实际上，函数的递归调用存放的结构就是栈）
先实现步骤1：
public int getBottom(Stack<Integer> stack) {
//栈顶依次往下弹出元素，栈为空时，说明已经到栈底，则返回该栈底元素
int res = stack.pop();
if(stack.empty()) { //A
return res;
}else {
//未到栈底，则递归调用，继续往下找
int bottom = getBottom(stack); //尝试从这往里看，假设走到了 A，这个时候往外返回了最底部的元素，那么下一步需要做什么呢？
//下一步将需要将除栈底元素的其他元素全部入栈，及（1,2,3）->(1,2)
stack.push(res);
//并且将栈底元素往上返回
return bottom;;
}
}
步骤2，主方法reverse，首先思考一下它的终止条件是什么？即什么时候开始真正执行元素反转，显而易见，当通过getBottom获取完所有元素时（此时栈为空），可以开始元素重新入栈，实现元素逆序。
public void reverse(Stack<Integer> stack) {
if(stack.empty()) {
return;
}
//递归获取栈底元素，该函数最里层（即首先返回的元素的顺序从自底向上），也就是说，不能在下面直接写stack.push，需要再递归
int i = get(stack);
reverse(stack);
stack.push(i);
}
2.4 实现栈的排序
只允许使用一个辅助栈和变量，实现将栈中元素自顶向下从大到小的排序。
思路：记原栈为stack，辅助栈为help，操作如下
stack不为空时，弹出栈顶元素a，若help为空或help栈顶元素小于a则直接入help。否则将help栈顶元素不断弹出，直到help为空或栈顶元素小于a才将a入help。
TO BE CONTINUE...