数据结构学习

import java.util.Stack;

/**
 * Created by 刘逗逼 on 2016/2/25.
 * java中没有指针，不能像c那样有队首队尾指针来指示，要想实现队列先入先出的特点，可以用两个栈来模拟
 * 一个栈用来入，当需要出时再把它一个个转移到另外一个栈中，那么那些元素在两个栈中的顺序就刚好相反，这样就可以用栈来
 * 后入先出来模拟队列的先入先出了
 */
public class Queue<T> {
    private Stack<T> in=null;
    private Stack<T> out=null;
    private int count;
    public Queue(){
        in=new Stack<T>();
        out=new Stack<T>();
        count=0;
    }
    //当需要向队列添加数据时：1.将“已有的全部数据”都移到in中。2.将“新添加的数据”添加到in中。
    public void add(T type){
        while (!out.isEmpty()){           //当其中一个栈为空时，另外一个栈就装着所有元素，若该栈为in时，那么此时元素的顺序
                                          // 则为进入队列的顺序，若为out时，则为出队列的顺序
            in.push(out.pop());           //把out栈中的所有元素移到in栈中去
        }
        in.push(type);
        count++;
    }
    //当需要从队列获取元素时：1.将“已有的全部数据”都移到out中.2.返回并删除out栈顶元素。
    public T get(){
        while (!in.isEmpty()){
            out.push(in.pop());
        }
        count--;
        return out.pop();
    }
    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }
    public static void main(String[] args){
        Queue<String> stringQueue=new Queue<String>();
        stringQueue.add("可");
        stringQueue.add("以");
        stringQueue.add("清");
        stringQueue.add("心");
        stringQueue.add("也");
        while (!stringQueue.isEmpty()){
            System.out.print(stringQueue.get());
        }
        System.out.println();
        System.out.println("the Queue size is "+stringQueue.size());
    }
}

import java.lang.reflect.Array;

/**
 * Created by 刘逗逼 on 2016/2/24.
 * 数组实现的栈，能存储任意类型的数据
 */
public class Stack<T> {
    private static final int defaultSize=12;
    private T[] stacks;
    private int count;
    public Stack(Class<T> type){
        this(type,defaultSize);
    }
    public Stack(Class<T> type,int size){
        stacks=(T[]) Array.newInstance(type,size);
        count=-1;           //-1表示在栈为空
                            //c中是用栈顶指针来指示栈顶，java只能用计数来指示栈顶位置
    }
    //将value加到栈顶
    public void push(T value){
        stacks[++count]=value;
    }
    //返回栈顶元素
    public T peek(){
        return stacks[count];
    }
    //返回栈顶元素并删除栈顶元素
    public T pop(){
        return stacks[count--];

    }
    //返回栈的大小
    public int size(){
        return stacks.length;
    }
    //返回栈是否为空
    public boolean isEmpty(){
        return size()==0;
    }
    //打印栈
    public void printStack(){
        if(isEmpty()){
            System.out.println("Stacks is empty!");
        }else {
            System.out.println("Stacks size is "+size());
            int i=size()-1;
            while (i>=0){
                System.out.println(stacks[i--]);
            }
        }
    }

    public static void main(String[] args){
        Stack<String> stringStack = new Stack<String>(String.class);
        stringStack.push("1");
        stringStack.push("2");
        stringStack.push("3");
        stringStack.push("4");
        System.out.println(stringStack.peek());
        System.out.println(stringStack.pop());
        System.out.println("Stacks size is "+stringStack.size());
        System.out.println(stringStack.isEmpty());
        stringStack.printStack();
    }
}

/**
 *Java 实现的双向链表
 * Created by 刘逗逼 on 2016/2/23.
 */
public class DoubleLink<T> {
    private DNode<T> head;               //首节点
    private int count;                   //节点数

    //节点     某个类的属性类型不确定时使用泛型，相当于加了个括弧说明
    private class DNode<T>{              //c中是结构体，在java中就是类了, 因为节点值类型不确定，所以用泛型避免用object类
        private DNode<T> prev;           //prev是引用，相当于c的指针
        private DNode<T> next;
        private T value;
        public DNode(T value,DNode prev,DNode next){
            this.value=value;
            this.prev=prev;
            this.next=next;
        }
    }

    public DoubleLink(){
        //创建表头
        head=new DNode<T>(null,null,null);
        head.prev=head.next=head;              //完成表头的初始化
        count=0;
    }
    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }
    public DNode<T> getNode(int index){
        if(index<0||index>=count)
            throw new IndexOutOfBoundsException();
        //根据index位置决定正向还是反向查找，因为其是双向的，正向为head的next，反向为head的prev
        if(index<count/2){                    //正向
            DNode<T> node=head.next;
            for (int i=0;i<index;i++){
                node=node.next;
                return node;
            }
        }
        DNode<T> node=head.prev;
        int rindex=count-index-1;       //反向第几个
        for (int i=0;i<rindex;i++){
            node=node.prev;
        }
        return node;
    }
    public T get(int index){
        return getNode(index).value;
    }
    public T getFirst(){
        return getNode(0).value;
    }
    public T getLast(){
        return getNode(count-1).value;
    }
    public void insert(int index,T type){
        if (index==0) {
            DNode<T> node=new DNode<T>(type,head,head.next);
            head.next.prev=node;
            head.next=node;
            count++;
        } else {
            DNode<T> node =getNode(index);
            DNode<T> goal=new DNode<T>(type,node.prev,node);
            node.prev.next=goal;
            node.prev=goal;
            count++;
        }
    }
    public void insertFirst(T type){
        insert(0,type);     //因为在insert中针对index=0进行了判断
        count++;
    }
    public void appendLast(T type){
        DNode<T> node=new DNode<T>(type,head.prev,head);
        head.prev.next=node;
        head.next=node;
        count++;
    }
    public void del(int index){
        DNode<T> node=getNode(index);
        node.next.prev=node.prev;
        node.prev.next=node.next;
        node=null;
        count--;
    }
    public void delFirst(){
        del(0);
    }
    public void delLast(){
        del(count-1);
    }
}