算法（第四版）之第一章

二分查找

import java.util.Arrays;
public class BinarySearch {
    public static int rank(int key,int a[]){
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi){
            int mid = lo + (hi-lo)/2;
            if (key < a[mid]) hi = mid -1;
            else if(key > a[mid]) lo = mid +1;
            else return mid;

        }
        return -1;
    }
    public static void main(String[] args){
        int[] whitelist = {1,5,4,3,2,9,8,6,7};
        Arrays.sort(whitelist);
        int[] mess = {1,2,3,4,5,6,7,8,9,10,11,12};
        for(int i = 0;i < mess.length;i++){
            int key = mess[i];
            if(rank(key,whitelist) < 0)
                StdOut.println(key);//打印不在whitelist中的内容
        }
    }
}

双栈算术表达式

import java.util.Stack;

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        StdOut.println("请输入表达式：");
        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(")")) {
                double v = vals.pop();
                String op = ops.pop();
                if (op.equals("+")) v = v + vals.pop();
                if (op.equals("-")) v = vals.pop() - v;
                if (op.equals("*")) v = v * vals.pop();
                if (op.equals("/")) v = vals.pop() / v;
                if (op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            } else {
                vals.push(Double.parseDouble(s));
                double temp = vals.lastElement();

            }

        }
        StdOut.println(vals.pop());
    }
}

尼玛，IDEA的EOF要按^D.曹

泛型栈

public class FixedCapacityStack<Item> {
    private Item[] a;
    private int N;

    public FixedCapacityStack(int size) {
        a = (Item[]) new Object[size];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public void push(Item item) {
        if(N == a.length) resize(2*a.length);
        a[N++] = item;
    }

    public Item pop() {
        Item item = a[--N];
        a[N] = null;//避免对象游离；
        if(N > 0&& N == a.length/4) resize(a.length/2);
        return item;
    }

    public int size() {
        return N;
    }

    public void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for(int i = 0;i < N;i++)
            temp[i] = a[i];
        a = temp;
    }


    public static void main(String[] args) {
        FixedCapacityStack<String> s;
        s = new FixedCapacityStack<String>(100);

        while (!StdIn.isEmpty()) {
            String temp = StdIn.readString();
            if(!temp.equals("-")){
                s.push(temp);
            }
            else if(!s.isEmpty())
                StdOut.print(s.pop()+" ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}

​ java的垃圾手机策略是回收所有无法被访问的对象的内存。在我们对pop（）的实现中，被弹出的元素仍然存在于数组中。这个元素实际上已经是个故而了—它永远也不会再次被访问了，但垃圾回收器无法知道这一点，除非该引用被覆盖。此时我们只需将该数组元素设置为null即可将其覆盖，并回收内存。