棧

特點：先進后出

用數(shù)組實現(xiàn)

public class MyStack<T>{
    private T[] stack;
    private int size;
    public static final int INIT_SIZE = 5;

    public MyStack(){
        stack = (T[]) new Object[INIT_SIZE];// 注意泛型數(shù)組的使用
    }

    public void push(T element){
        ensureCapacityHelper(size + 1);
        stack[size++] = element;
    }

    private void ensureCapacityHelper(int minCapacity) {
        if (minCapacity > stack.length) {
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity) {
        int newLength = (int) (stack.length * 1.5);
        stack = Arrays.copyOf(stack,newLength);
    }

    public T pop(){
        T element = peek();
        if(size > 0){
            stack[size - 1] = null;
            size--;
        }
        return element;
    }

    public boolean isEmpty(){
        return this.size == 0;
    }

    public T peek(){
        if(size > 0){
            return stack[size - 1];
        } else{
            return null;
        }
    }

}

用鏈表實現(xiàn)

public class MyStack<T>{

    private Node<T> head;

    class Node<T>{
        private T data;
        private Node<T> next;

        public Node(T data,Node<T> next){
            this.data = data;
            this.next = next;
        }
    }

    public MyStack(){

    }

    public void push(T element){
        if (element == null) {
            return;
        }
        if (this.head == null) {// 棧為空
            Node node = new Node<T>(element, null);
            head = node;
        } else {
            Node node = new Node<T>(element, null);
            node.next = head;

            head = node;
        }
    }

    public T pop(){
        T element = peek();
        if(head != null){
            head = head.next;
        }
        return element;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public T peek(){
        if(head != null){
            return head.data;
        } else{
            return null;
        }
    }

}

逆波蘭表達式

a * 2 // 需要6個指令集
a << 1 // 只需要1個指令集

標準四則運算表達式——中綴表達式
9+(3 - 1) * 3 + 10/ 2
計算機采用——后綴表達式
9 3 1 - 3 * + 10 2 / +

遞歸

大問題分解成小問題拧略，都可以用遞歸

/**
     * 輸入3成艘，輸出為：3决瞳，2，1癣丧，0肥败，-1族跛，0烤芦，1举娩，2，3
     *
     * 實參與形參的傳遞
     * @param n
     */
    public void recursionDemo(int n){
        System.out.println(n);
        if (n < 0) {
            return;
        } else {
            recursionDemo(n-1);
            System.out.println(n);
        }
    }

斐波那契數(shù)列

    /**
     * 有一對兔子，從出生后3個月晓铆，每個月生一對兔子，小兔子長到三個月又生一對兔子绰播，
     * 假如兔子不死骄噪，問第二十個月兔子對數(shù)
     * 第一個月兔子1對，第二個月1對蠢箩，第三個月2對链蕊，第四個月3對，第五個月5對谬泌，第六個月8對
     * 從第三個月開始滔韵，兔子對數(shù)是前兩個月之和（斐波那契數(shù)列）
     * @param n
     */
    public int fibonacci(int n){
        if (n < 0) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }

漢諾塔問題

 public void hanoi(int n,char from,char temp,char to){
    if(n == 1){// 一個盤子的情況
        System.out.println(n+" "+from+" ---> "+to);
    } else{
        //  首先 ，把上面的n-1個盤子移動到中間的柱子temp上
        hanoi(n-1,from,to,temp);
        //  然后掌实，把 第n個 盤子移動到最終的柱子to上
        System.out.println(n+" "+from+" ---> "+to);
        //  最后陪蜻，把temp上的n-1個盤子從temp借助最開始的柱子from全部移動到to上
        hanoi(n-1,temp,from,to);
    }
 }