java数据结构和算法02（栈）

　　什么叫做栈（stack）呢？这里的栈和jvm的java栈可不是一个东西。。。

　　栈作为一种数据结构，我感觉栈就类似一种接口，实现的话有很多种，比如用数组、集合、链表都可以实现栈的功能，栈最大的特点就是先进后出，可以想象一下放羽毛球的盒子怎么放进羽毛球和拿出来羽毛球，我们把放进羽毛球的动作就叫做压栈或者入栈（push）,拿出羽毛球的动作就叫做弹栈或出栈（pop）

　　其实在java中已经有个栈的实现了，就是stack，我们简单用一下：

package com.wyq.thread;

import java.util.stack;

public class mystack {
    public static void main(string[] args) {
        stack<object> stack = new stack<object>();
        stack.push("老王");
        stack.push(123);
        stack.push(false);
        stack.push('a');
        system.out.println(stack.tostring());
        
        for (int i = 0; i < 4; i++) {
            system.out.println(stack.pop());
        }
    }
}

　这个stack默认使用集合实现的，这个类是继承了vector，而vector这个类就是一个集合，实现了list接口的，而且我们还知道这个vector这个类是线程安全的，每个方法都加了synchronized关键字，所以也就是说效率不会怎么高。我们可以试试用数组来自己简单实现一个栈，可能就对栈这种数据结构有点了解了，为什么栈是先进后出的呢？假如我们要实现怎么才能实现这种进出方式呢？

　　在我们实现的栈中我不会实心扩容的，因为逻辑一多就容易弄混，但是我还是将扩容的原理说一下：

　　假如有一个最大容量是20数组a，还会有个负载因子一般是0.75，这个负载因子干什么用的呢？

　　这个0.75就是a/b得出来的，虽然可以修改这个0.75这个值，但是据说0.75是最稳定的最好不要修改这个值；

　　当我们往a数组中放数据，当放了20*0.75=15个数据之后，此时这个数组就会收到一个警报，快装满了，赶紧想想办法，于是啊，又创建出了一个比20更大的数组，假设是40容量的数组b，然后我们就把a数组中的所有数据都复制到b数组中，再把指向数组a的引用修改为指向数组b的引用就ok了，如下图所示：

 

　　我们自己实现的栈为了简洁起见，越简洁越好，就不弄这些花里胡哨的东西了，怎么简单怎么来，想进行扩容的小伙伴可以自己添加扩容方法；

　　顺便说一个简单的东西，++n和n++，--n和n--的区别:比如value = ++n，这表示n先+1再赋值给value，比如value = n++,这就表示n先赋值给value，然后n再+1

package com.wyq.thread;

import java.util.arrays;

public class mystack {
    private object[] arr;
    //数组中最大的容量
    private int maxlength;
    //指向栈顶的元素，也就是指向数组最后一个位置的元素
    private int top;
    
    //调用有参构造，默认是10个容量的数组
    public mystack(){
        this(10);
    }
    public mystack(int len){
        this.maxlength = len;
        arr = new object[maxlength];
        top = -1;//因为刚开始数组中没有数据，我们把top=-1表示数组中没有元素
    }
    //压栈，首先要保证top的值不能大于最大的索引，不然数据都放到数组外面了
    //要想将一个数据丢进栈中，先将top往后往后移动一个位置，然后在这个位置放入数据
    public void push(object obj){
        if (top<maxlength-1) {
            arr[++top] = obj;
            
        }
    }
    //弹栈，首先找到栈顶的元素，这个peek（）方法就在下面，将这个栈顶的元素返回，然后经数组最后一个数据变为null
    //最后就是将top往前移动一个位置，确保top始终指向的是栈顶元素（数组最后一个元素）
    public object pop(){
        object peek = peek();
        arr[top--]=null;
        return peek;
    }
    //查询栈顶的数据，注意此时并没有弹栈，我们只是想看看栈顶是什么东西
    public object peek(){
        return arr[top];
    }
    //重写tostring方法，更好的进行展示栈中的数据
    @override
    public string tostring() {
        return arrays.tostring(arr)+"]";
    }
    public static void main(string[] args) {
        mystack stack = new mystack();
        stack.push("老王");
        stack.push(123);
        stack.push(false);
        stack.push('a');
        system.out.println(stack.tostring());
        
        for (int i = 0; i < 4; i++) {
            system.out.println(stack.pop());
        }
    }
}

 

　　感觉比上一篇的array容易不少啊.....