重新翻开数据结构书

序

去年在二手书网店买课本的时候看到本java数据结构书，一直没看,最近翻出来看看，书如下图，看上去是哪个大学的课本，第一章概念里还有画线笔记

表

• 略

栈和队列

栈的实现

• 发现按我的思路写的代码比书上的代码短不少，只有书上的三分之一

public interface Stack<T> {
    //入栈
    void push(T data);
    //输出并删除
    T  pop();
    //size
    int size();

    default boolean isEmpty(){
        return size() == 0;
    }
}

//顺序栈实现
public class SeqStack<T> implements Stack<T>{
    private Object[] stackArray;
    private  int size;
    private final static int MAX_SIZE = 1024 * 1024;

    //初始化
    public SeqStack(){
        size = 0;
        stackArray =  new Object[16];
    }
    @Override
    public void push(T data) {
        if(size() == MAX_SIZE) throw new IllegalArgumentException("over max size");
        //判断是否超出数组，超出数组就扩
        if(size == stackArray.length){
            stackArrayExtend();
        }
        stackArray[size] = data;
        size++;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T pop() {
        //size为0时不能pop
        if(isEmpty()){
            throw new IllegalArgumentException("empty static can not pop");
        }
        var tmp = stackArray[size-1];
        stackArray[size-1] = null; //clear
        size--;
        return (T) tmp;
    }

    @Override
    public int size() {
        return this.size;
    }

    private  synchronized   void stackArrayExtend(){
        int extendArrayLength = stackArray.length * 2;
        var stackArrayTmp = new Object[extendArrayLength];
        for (int i = 0; i < size ; i++) {
            stackArrayTmp[i] = stackArray[i];
        }
        this.stackArray =  stackArrayTmp;
    }
}
//链栈的实现
public class LinkStack<T> implements Stack<T> {
    private LinkStack<T> next;
    private T data;
    private int size;

    public LinkStack(){
    }

    @Override
    public void push(T data) {
        //每次新来上个，都复制自己到下一个上去
        LinkStack<T> next = new LinkStack<>();
        next.size = this.size;
        next.data = this.data;
        next.next = this.next;
        this.next = next;
        this.data = data;
        this.size += 1;
    }

    @Override
    public T pop() {
        if(this.size == 0) throw  new IllegalArgumentException("empty stack can not pop");
        var data = this.data;
        this.data = next.data;
        this.size = next.size;
        this.next = next.next;
        return data;
    }

    @Override
    public int size() {
        return this.size;
    }
}

栈的应用

十进制转换二进制，8进制，16进制

• 实现

    //十进制转其他进制
    public static String convertDec(Integer number,Integer system){
        if(number < 0) throw new IllegalArgumentException("只能转换大于0的数");
        if(number < system) return "" + number;
        Stack<Integer> stack = new SeqStack<>();  //顺序栈和链栈都可以
        //相除取余进栈
        while (true){
            var  remainder  = number % system;
            stack.push(remainder);
            number = number / system;
            if(number < system && number!= 0){
                stack.push(number);
                break;
            }
        }
        var result = "";
        while (!stack.isEmpty()) result += stack.pop();
        return result;
    }

• spock测试用例

class StackApplyTest extends Specification {
    @Unroll
    def "convertDec2BinTest"() {
        expect:
            def result = StackApply.convertDec(number,system)
            println result
            if(system == 2) {
                result == Integer.toBinaryString(number)
            }else if(system == 8){
                result == Integer.toOctalString(number)
            }
        where:
        number|system
        10|2
        10|8
        1111|8
        2222|8
        1|2
        16|8

    }
}

括号匹配问题

• 实现

    //括号是否匹配问题，碰到左边括号进栈，碰到右边括号和出栈括号对比
    //{[(
    public static boolean checkBrackets(String input){
        if( input == null || input.equals("")) throw new IllegalArgumentException("empty string");
        var leftBrackets = "{[(";
        var rightBrackets = "}])";
        Stack<String> stack = new LinkStack<>();
        for (int i = 0; i < input.length(); i++) {
            var item = input.substring(i,i+1);
            if(leftBrackets.contains(item)){
                stack.push(item);
            }
            if(rightBrackets.contains(item)){
                //直接映射判断
                if(leftBrackets.indexOf(stack.pop())  != rightBrackets.indexOf(item)) return false;
            }
        }
        return true;
    }

• spock 测试用例

    def "checkBracketsTest"(){
        expect:
            def result = StackApply.checkBrackets(input)
            result == expectResult
        where:
        input|expectResult
        "{(1)11}"|true
        "{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}"|true
        "{(111}"|false
    }

队列实现

树

实现

• 每个节点记录左右子节点

图

查找

排序