二叉树的遍历、查找、插入、删除等

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月29日 下午11:33:24
 * ******************************************/
package ren.laughing.code.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树
 * 
 * @author Laughing_Lz
 *
 */
public class Tree {

    /**
     * 前序遍历二叉树
     * 
     * @param root
     */
    public static void preOrder(Node root{
        if (root == null) {
            return;
        }
        System.out.print(root.getValue() + " ");
        if (root.getLeft() != null) {
            preOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            preOrder(root.getRight());
        }
    }

    /**
     * 中序遍历二叉树
     * 
     * @param root
     */
    public static void inOrder(Node root{
        if (root == null) {
            return;
        }
        if (root.getLeft() != null) {
            inOrder(root.getLeft());
        }
        System.out.print(root.getValue() + " ");
        if (root.getRight() != null) {
            inOrder(root.getRight());
        }
    }

    /**
     * 后序遍历二叉树
     * 
     * @param root
     */
    public static void postOrder(Node root{
        if (root == null) {
            return;
        }
        if (root.getLeft() != null) {
            postOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            postOrder(root.getRight());
        }
        System.out.print(root.getValue() + " ");
    }

    /**
     * 层次遍历二叉树
     * 
     * @param root
     */
    public static void levelOrder(Node root{
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            System.out.print(currentNode.getValue() + " ");
            if (currentNode.getLeft() != null) {
                queue.add(currentNode.getLeft());
            }
            if (currentNode.getRight() != null) {
                queue.add(currentNode.getRight());
            }
        }
    }

    /**
     * 卡特兰数: 给定一组数据,比如 1,3,5,6,9,10。你来算算,可以构建出多少种不同的二叉树?
     * https://en.wikipedia.org/wiki/Catalan_number
     * 
     * @param numKeys
     * @return
     */
    public static int countTrees(int numKeys{
        if (numKeys <= 1) {
            return (1);
        } else {
            int sum = 0;
            int left, right, root;
            // 每次迭代,root节点的左右两颗子树的节点数不同--左子树的节点数从0到numKeys-1,右子树相反
            // 这样迭代结束后,各种情况便都覆盖全了;
            for (root = 1; root <= numKeys; root++) {
                left = countTrees(root - 1);
                right = countTrees(numKeys - root);

                // number of possible trees with this root == left*right
                sum += left * right;
            }
            return (sum);
        }
    }

    static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value{
            super();
            this.value = value;
        }

        public Node() {
            super();
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left{
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right{
            this.right = right;
        }

        public void setValue(int value{
            this.value = value;
        }

        public int getValue() {
            return this.value;
        }
    }

    /**
     * 二叉查找树的查找操作 二叉查找树:每个节点的左节点都比当前节点值小,右节点都比当前节点大值。
     * 
     * @param root
     * @param value
     * @return
     */
    public static Node find(Node root, int value{
        if (root == null) {
            return null;
        }
        while (root != null) {
            if (root.getValue() == value) {
                return root;
            } else if (root.getValue() > value) {
                root = root.getLeft();
            } else if (root.getValue() < value) {
                root = root.getRight();
            }
        }
        return null;
    }

    /**
     * 二叉查找树的插入操作
     * 
     * @param root
     * @param value
     */
    public static void insert(Node root, int value{
        if (root == null) {
            root = new Node(value);
        }
        while (root != null) {
            if (root.getValue() < value) {
                if (root.getRight() == null) {
                    root.setRight(new Node(value));
                    return;
                }
                root = root.getRight();
            } else if (root.getValue() > value) {
                if (root.getLeft() == null) {
                    root.setLeft(new Node(value));
                    return;
                }
                root = root.getLeft();
            }
        }
    }

    /**
     * 二叉查找树的删除操作,要注意有三种情况:1、待删除节点没有子节点2、待删除节点只有一个子节点(只需更新父节点)
     * 3、待删除节点有两个子节点(从待删除节点的左子节点中找出最大的节点替换,或从右子节点中找出最小的节点替换)
     * 
     * @param tree
     * @param data
     */
    public static void delete(Node tree, int data{
        Node p = tree; // p 指向要删除的节点,初始化指向根节点
        Node pp = null// pp 记录的是 p 的父节点
        while (p != null && p.getValue() != data) {
            pp = p;
            if (data > p.getValue())
                p = p.right;
            else
                p = p.left;
        }
        if (p == null)
            return// 没有找到

        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) { // 查找右子树中最小节点
            Node minP = p.right;
            Node minPP = p; // minPP 表示 minP 的父节点
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.setValue(minP.getValue()); // 将 minP 的数据替换到 p 中
            p = minP; // 下面就变成了删除 minP 了
            pp = minPP;
        }

        // 删除节点是叶子节点或者仅有一个子节点
        Node child; // p 的子节点
        if (p.left != null)
            child = p.left;
        else if (p.right != null)
            child = p.right;
        else
            child = null;

        if (pp == null)
            tree = child; // 删除的是根节点
        else if (pp.left == p)
            pp.left = child;
        else
            pp.right = child;

        System.out.println("\n删除节点" + data + "后:");
        inOrder(tree);
    }

    /**
     * 计算二叉树的高度
     *
     * @param root
     * @param index
     * @return
     */
    public static int getBinaryLevel(Node root, int index{
        if (null == root) {
            return index;
        }

        int maxleftLevel = 0;
        if (root.left != null) {
            maxleftLevel = getBinaryLevel(root.left, index + 1);
        }

        int maxRightLevel = 0;

        if (root.right != null) {
            maxRightLevel = getBinaryLevel(root.right, index + 1);
        }

        return Math.max(maxleftLevel, maxRightLevel) + 1;
    }

    public static void main(String[] args{
        // 构建二叉树
        Node leaf1 = new Node(6);
        Node leaf2 = new Node(9);
        Node leaf3 = new Node(10);
        Node node1 = new Node(3);
        node1.setLeft(leaf1);
        node1.setRight(leaf2);
        Node node2 = new Node(5);
        node2.setLeft(leaf3);
        Node root = new Node(1);
        root.setLeft(node1);
        root.setRight(node2);
        // 构建中序遍历有序的二叉查找树
        Node leaf11 = new Node(1);
        Node leaf22 = new Node(5);
        Node leaf33 = new Node(9);
        Node node11 = new Node(3);
        node11.setLeft(leaf11);
        node11.setRight(leaf22);
        Node node22 = new Node(10);
        node22.setLeft(leaf33);
        Node root1 = new Node(6);
        root1.setLeft(node11);
        root1.setRight(node22);

        System.out.println("前序遍历:");
        preOrder(root);
        System.out.println("\n中序遍历:");
        inOrder(root);
        System.out.println("\n后序遍历:");
        postOrder(root);
        System.out.println("\n层次遍历:");
        levelOrder(root);
        System.out.print("\n计算卡特兰数:\n" + countTrees(3));
        System.out.print("\n二叉查找树的查找操作:\n" + find(root1, 6).value);
        System.out.print("\n计算二叉树高度:\n" + getBinaryLevel(root, 0));
        System.out.println("\n二叉查找树的插入操作:");
        insert(root1, 11);
        System.out.println("\n二叉查找树插入节点11后:");
        inOrder(root1);
        System.out.println("\n二叉查找树的删除操作:");
        delete(root1, 6);
    }
}

哈希冲突、散列表学习记录

 1/********************************************
 2 * All Rights Reserved By www.laughing.ren
 3 * @author:Laughing_Lz
 4 * @version:2018年11月27日 上午1:07:01
 5 * ******************************************/
 6package ren.laughing.code.Test;
 7
 8import java.util.HashMap;
 9import java.util.LinkedHashMap;
10import java.util.Map;
11import java.util.TreeMap;
12
13public class Hash {
14    class Son {
15        private int age;
16        private String name;
17    }
18
19    /*
20     * ThreadLocalMap 使用了开放寻址法处理hash冲突 数据量小,装载因子小(较于链表更浪费内存空间)
21     * 开放寻址法的数据都存储在数组中,可以有效利用CPU缓存加快查询,而且序列化较为简单。
22     * 删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且,在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。所以,
23     * 使用开放寻址法解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
24     */
25    public static void hash() {
26        // ThreadLocalMap是ThreadLocal的内部类,它是一个Map,key是ThreadLocal的实例变量
27        ThreadLocal<Son> threadLocal = new ThreadLocal<Son>();
28        // 使用链表法解决hash冲突,适用于大对象,大数据量,装载因子可以大于1,使用灵活,可将链表转换为红黑树、跳表等结构。
29        LinkedHashMap<String, Son> linkedHashMap = new LinkedHashMap<>();
30        HashMap<String, Son> map = new HashMap<String, Son>();
31        // hashmap 可修改初始大小,默认为16,装载因子默认0.75
32        HashMap<ObjectObject> hashMap = new HashMap<ObjectObject>(110);
33    }
34    /*
35     * 设计工业级的散列表,应具有哪些属性? 1.支持快速查询、插入、删除 2.内存占用合理,不能浪费过多的内存空间
36     * 3.性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况
37     */
38
39    /*
40     * 如何设计工业级的散列表? 1.设计一个合理的散列函数 2.定义装载因子阈值,并且设计动态扩容策略 3.选择合适的散列冲突解决方法
41     */
42
43    /*
44     * 集合类的带hash的,例如hashmap、hashset、hashtable等。
45     * hashmap中散列函数是key的hashcode与key的hashcode右移16位异或,这是为了把key的高位考虑进去,如果key是0,hash值为0
46     * 。在put的时候,如果表没有初始化,需要初始化下,在计算key的位置的时候很巧妙,使用表的length-1和key的hash值与计算的,
47     * 实际上就是对key的hash值对表长取模,基于hashmap是2的幂次方特性,这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*
48     * 负载因子,就会自动扩容,默认是两倍,自动扩容方法是将key的hash与表长直接与判断是否有高位,有高位就把这个node放到新表里旧表对应位置加旧表长的地方
49     * 。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数,赋值为integer
50     * .max。hashmap采用的是链地址法结合红黑树解决hash冲突,当桶中链表长度大于8就会将桶中数据结构转化为红黑树。
51     * hashtable默认的初使容量11,负载因子也是0.75,如果要指定初始化hashtable容量最好是给一个素数。
52     * 这是因为放入table的时候需要对表长取模,尽量分散地映射。hashtable通过链地址法解决hash冲突,当数据容量大于数据容量*负载因子自动扩容,
53     * 扩容原表长两倍+1。
54     */
55    /*
56     * TreeMap 使用红黑树的数据结构,好好研究源码
57     */
58    Map<StringString> map = new TreeMap<>();
59}

关于二分查找及变体

关于二分查找及变体

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月22日 下午11:28:28
 * ******************************************/
package ren.laughing.code.Test;

import java.util.Arrays;

public class Search {

    /**
     * 简单的二分查找,前提是数组是有序,且无重复值
     * 
     * @param arr arr
     */
    public static int binarySearch(int valueint[] arr{
        int low = 0, high = arr.length - 1, middle;
        // 为什么要是<=呢?
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] < value) {
                low = middle + 1;
            } else if (arr[middle] > value) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;

    }

    /**
     * 递归方法实现简单二分查找,前提同上:数组有序,且无重复值
     * 
     * @param value value
     * @param arr   arr
     * @param low   low
     * @param high  high
     * @return
     */
    public static int recursionBinarySearch(int valueint[] arr, int low, int high{
        if (low > high) {
            return -1;
        }
        int middle = low + ((high - low) >> 1);
        if (arr[middle] == value) {
            return middle;
        } else if (arr[middle] > value) {
            return recursionBinarySearch(value, arr, low, middle - 1);
        } else {
            return recursionBinarySearch(value, arr, middle + 1, high);
        }

    }

    /**
     * 求解一个数的平方根,精确到小数六位
     * 
     * @param n n
     * @return
     */
    public static float square(float n{
        if (n == 0 || n == 1) {
            return 1;
        }
        float low = 0, high = n;
        float middle = low + (high - low) / 2;
        while (Math.abs(middle * middle - n) > 0.000001) {
            if (middle * middle > n) {
                high = middle;
            } else if (middle * middle < n) {
                low = middle;
            } else {
                return middle;
            }
            middle = low + (high - low) / 2;
        }
        return middle;
    }

    /**
     * 利用二分查找返回数组中第一个出现value的位置,注意边界条件middle==0
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == 0) || (arr[middle - 1] < value)) {
                    return middle;
                } else {
                    high = middle - 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个出现value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low < high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == arr.length - 1) || (arr[middle + 1] > value)) {
                    return middle;
                } else {
                    low = middle + 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;

    }

    /**
     * 利用二分查找返回数组中第一个大于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstGreat(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value && arr[middle - 1] <= value) {
                return middle;
            } else if (arr[middle] <= value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个小于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastLess(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] < value && arr[middle + 1] >= value) {
                return middle;
            } else if (arr[middle] >= value) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 循环数组中使用二分查找获取value所在位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int loopBinarySearch(int[] arr, int value{
        if(arr.length < 1) {
            return -1;
        }
        if (arr.length == 1) {
            if (arr[0] == value) {
                return 0;
            } else {
                return -1;
            }
        }
        int low = 0, high = arr.length, middle = 0;
        // 首先获取首末位置
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                high = i;
                low = i + 1;
            }
        }
        if (arr[arr.length - 1] > arr[0]) {
            low = 0;
            high = arr.length - 1;
        }
        // 经过和arr[0]判断后筛选出可能包含value的子数组
        if (arr[0] == value) {
            return 0;
        } else if (arr[0] < value) {
            low = 1;
        } else if (arr[0] > value) {
            high = arr.length - 1;
        }
        // 使用简单二分查找获取value位置
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args{
        int[] arr = { 2146730985 };
        Arrays.sort(arr);
//        System.out.println(binarySearch(5, arr));
//        System.out.println(recursionBinarySearch(5, arr, 0, arr.length - 1));
        System.out.println(square(5f));
        int[] arr1 = { 01234455589 };
        System.out.println(firstEqual(arr1, 5));
        System.out.println(lastEqual(arr1, 5));
        System.out.println(firstGreat(arr1, 5));
        System.out.println(lastLess(arr1, 5));
        int[] arr2 = { 7890123456 };
        System.out.println(loopBinarySearch(arr2, 8));

    }
}

五种排序算法的比较

五种排序算法的比较:
冒泡排序、插入排序、选择排序均是原地排序,即空间复杂度为O(1),平均时间复杂度O(n^2)
其中选择排序最好最坏均是O(n*n),但它不是稳定的,因此不如插入排序更受欢迎

归并排序:时间复杂度为在任何情况下都O(nlogn),归并是稳定的、但并不是原地排序,它使用了临时数组,即空间复杂度为O(n)
快速排序:大部分情况下时间复杂度为O(nlogn),极端情况下为O(n^2),主要考虑分区点的选取。快排不是稳定的,是原地排序,空间复杂度为O(1)

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月21日 下午9:47:08
 * ******************************************/
package ren.laughing.code.Sort;

public class Sort {

    /**
     * 冒泡排序
     * 
     * @param arr arr
     */
    public static void bubbleSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                // 循环判断,把大数浮上去
                if (arr[j + 1] < arr[j]) {
                    // swap
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     * 
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length - 1; i++) {
            int j = i + 1;
            int flag = arr[j];
            for (; j > 0; j--) {
                if (arr[j - 1] > flag) {
                    // 每次插入前,较大的其他元素均后移
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = flag;
        }
    }

    /**
     * 选择排序:交换的是位置
     * 
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < length - 1; i++) {
            // 记录最小值的位置
            int index = i;
            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            // 交换值,不稳定的排序
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }

    /**
     * 归并排序 递归
     * 
     * @param arr   arr
     * @param start start
     * @param end   end
     */
    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = start + (end - start) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle + 1, end);
        merge(arr, start, middle, end);
    }

    /**
     * 归并方法,将两个数组归并成一个有序数组
     * 
     * @param arr    arr
     * @param start  start
     * @param middle middle
     * @param end    end
     */
    private static void merge(int[] arr, int start, int middle, int end) {
        // 申请临时空间保存排序后的数组,排序后再还原至原数组arr
        int[] temp = new int[end - start + 1];
        int i = start, j = middle + 1, k = 0;
        while (i <= middle && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= middle) {
            temp[k++] = arr[i++];
        }
        while (j <= end) {
            temp[k++] = arr[j++];
        }
        // 赋值给原数组
        for (int t = 0; t < temp.length; t++) {
            arr[start + t] = temp[t];
        }
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        // 先找出中间点
        int partition = partition(arr, start, end);
        quickSort(arr, start, partition - 1);
        quickSort(arr, partition + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        // 分区点的选取是重点,这里选择末尾的点
        int flag = arr[end];
        int j = start;// 分区的最终位置
        for (int i = start; i < end; i++) {
            if (arr[i] < flag) {
                // 交换arr[i]和arr[j]
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
                j++;
            }
        }
        // 交换arr[j]和arr[end]
        int temp2 = arr[end];
        arr[end] = arr[j];
        arr[j] = temp2;
        return j;

    }

    public static void main(String[] args) {
        int[] arr = { 2452672803 };
        // bubbleSort(arr);
        // insertSort(arr);
        // selectSort(arr);
        // mergeSort(arr, 0, arr.length - 1);
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

下压堆栈的实现方式

算法第四版学习笔记一(下压堆栈的实现)

使用数组和链表两种实现方式
数组实现方式:

 1package ren.laughing.algorithms;
 2
 3import java.util.Iterator;
 4
 5/**
 6 * 下压堆栈(数组实现)
 7 * 
 8 * @author Laughing_Lz
 9 * @createTime 2018年9月2日
10 * @param <E>
11 */
12public class ResizingArrayStack<Eimplements Iterable<E{
13
14  private E[] items = (E[]) new Object[1];
15  private int N = 0;
16
17  public boolean isEmpty() {
18    return N == 0;
19  }
20
21  public int size() {
22    return N;
23  }
24
25  /**
26   * 动态调整数组大小 保持数组大小与栈大小之比小于一个常数
27   * 
28   * @param max 调整后的数组长度
29   */
30  public void resize(int max) {
31    E[] temp = (E[]) new Object[max];
32    for (int i = 0; i < N; i++) {
33      temp[i] = items[i];
34    }
35    items = temp;
36  }
37
38  public void push(E item) {
39    if (N == items.length) {
40      resize(2 * items.length);
41    }
42    items[N++] = item;
43  }
44
45  public E pop() {
46    E item = items[--N];
47    // 避免对象游离
48    items[N] = null;
49    if (N > 0 && N == items.length / 4) {
50      resize(items.length / 2);
51    }
52    return item;
53  }
54
55  /**
56   * 实现foreach遍历
57   */
58  @Override
59  public Iterator<E> iterator() {
60    return new StackIterator();
61  }
62
63  private class StackIterator implements Iterator<E{
64    private int i = N;
65
66    @Override
67    public boolean hasNext() {
68      return i > 0;
69    }
70
71    @Override
72    public E next() {
73      return items[--i];
74    }
75
76  }
77}

链表实现方式:

 1package ren.laughing.algorithms;
 2
 3import java.util.Iterator;
 4
 5/**
 6 * 下压堆栈(链表实现)
 7 * 
 8 * @author Laughing_Lz
 9 * @createTime 2018年9月2日
10 * @param <E>
11 */
12public class Stack<Eimplements Iterable<E{
13
14  private Node first;
15  private int N;
16
17  private class Node {
18    E item;
19    Node next;
20  }
21
22  public boolean isEmpty() {
23    return N == 0;
24  }
25
26  public int size() {
27    return N;
28  }
29
30  public void push(E item) {
31    Node oldfirst = first;
32    first = new Node();
33    first.item = item;
34    first.next = oldfirst;
35    N++;
36  }
37
38  public E pop() {
39    E item = first.item;
40    first = first.next;
41    N--;
42    return item;
43  }
44
45  /**
46   * 实现foreach遍历
47   */
48  @Override
49  public Iterator<E> iterator() {
50    return new StackIterator();
51  }
52
53  private class StackIterator implements Iterator<E{
54
55    private Node current = first;
56
57    @Override
58    public boolean hasNext() {
59      return first != null;
60    }
61
62    @Override
63    public E next() {
64      E item = current.item;
65      current = first.next;
66      return item;
67    }
68
69  }
70}