欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

深入理解Java 栈数据结构

程序员文章站 2022-03-30 17:40:49
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻 ......

  栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

  深入理解Java 栈数据结构

  从上图是基于数组实现的栈,可以看到,对栈的操作(压栈、出栈)其实都是对栈顶元素的操作,因此压栈和出栈的速度都比较快。栈中元素按照filo顺序排序的,即先入后出的规则,先放进去的元素最后才能被弹出来。

 

  一、栈结构要素

  1、栈,是用来存储数据的数据结构,可以使用数组或链表来实现栈结构

  2、栈顶,顾名思义栈最顶部的元素,压栈与出栈的对象

  3、栈深度,栈中数据多少,如果栈结构为数组,当栈长度大于等于数组长度后,会抛出异常或对数组进行扩容,栈结构是链表就没有这个限制。

  

//存放数据
    private object[] data;
    //数据量
    private int size;
    //栈顶
    private int top;
    //默认栈大小
    private static final int default_initial_capacity = 1 << 4;
    //最大容量
    private int maxcapacity;

  

  二、压栈

    /**
     * 向栈中放数据
     * @param obj
     * @return
     */
    public boolean push(object obj){
        if (size >= maxcapacity) return false;
        data[++top] = obj;
        size++;
        return true;
    }

  压栈操作比较简单,将新元素放在原栈顶的上面,栈顶指针往上移动一位。我这里当栈深度等于数组长度后是直接返回false的,当然根据实际的需求,你也可以对现有数组进行扩容,然后将原栈中元素放入新栈中即可。如:

     /**
     * 压栈,如果栈深度超出数组长度,将数组扩大1.5倍
     * @param obj
     * @return
     */
    public boolean push1(object obj){
        if (size >= maxcapacity){
            maxcapacity = maxcapacity * 3 / 2;
            object[] newstack = new object[maxcapacity];
            system.arraycopy(data,0,newstack,0,size);
            arrays.fill(data,null);
            data = newstack;
        }
        data[++top] = obj;
        size++;
        return true;
    }

 

  三、出栈

    /**
     * 从栈中弹出数据
     * @return
     */
    public object pop(){
        if (size <= 0) return null;
        size--;
        object old = data[top];
        data[top--] = null;
        return old;
    }

  出栈操作将栈顶元素掷为null,然后将栈顶指针往下移动一位即可,很简单。

 

  四、查看栈顶

    /**
     * 查看数据
     */
    public object peek(){
        if (isempty()) return null;
        return data[top];
    }

  这个方法更是简单到令人发指,只是查看栈顶元素,并没有将栈顶元素删除。

 

  五、清空栈

    /**
     * 清空栈数据
     */
    public void clear(){
        while (top > -1){
            data[top--] = null;
        }
        size = 0;
    }

 

  栈数据结构的实现基本已经讲完了,栈的基本操作差不多包包含在里面了,代码实现起来就是这么简单。另外,另一种基于链表的栈我就不再这里说了,因为也是很简单的,这是栈限定对链表的操作只能是操作链表头部,大家如果感兴趣的话可以自己尝试用链表实现一个栈,或者可以参考一下我之前写的基于链表实现的队列,原理是差不多的,也可以参考一下jdk中的linkedlist。