189 8069 5689

如何实现Stack栈

这篇文章主要讲解了“如何实现Stack栈”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何实现Stack栈”吧!

创新互联长期为数千家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为逊克企业提供专业的做网站、成都做网站,逊克网站改版等技术服务。拥有十余年丰富建站经验和众多成功案例,为您定制开发。

一,Stack源码分析

Stack,栈,也是数据结构的一种,对于java应用开发者而言,我使用栈的应用场景比较少,一般做做算法类的题会用到,对于实际的应用场景我觉得栈还是比较厉害的一种数据结构,栈的特点嘛,先进后出,后进先出。 

二,方法分析

其实,怎么说呢,我分析过了Vector集合的源码分析了,然而栈继承了Vector类,所以,你懂得,栈就是Vector集合的一种特例了,所以,这篇文章会很简短,但是我还是来分析了。

Vector集合最全面的源码分析 

2.1,栈结构继承结构

//记住和理解java类的"单继承,多实现"的特点哈
public class Stack extends Vector {}
   

2.2,构造函数

//一个无参构造函数
public Stack() {
   }
   

2.3,push()方法

其实,栈也是看作一种集合嘛,集合就是用来装填数据元素的嘛,所以我们接下来就是分析栈的各种方法了,如何装填数据元素呢,当然了,我们要看下push()方法了。

public E push(E item) {
   //看下第二步操作
       addElement(item);

       return item;
   }
//第二步操作
public synchronized void addElement(E obj) {
   //modCount的含义下面的这个解释已经很形象了
   //The number of times this list has been  modified
       modCount++;
   //这一步就是扩容操作了,这里不分析了,可以看下vector源码分析这篇文章
       ensureCapacityHelper(elementCount + 1);
   //将元素装填在数组中
       elementData[elementCount++] = obj;
   }
   

2.4,pop()方法

public synchronized E pop() {
       E       obj;
    //第二步操作,获取栈的大小
       int     len = size();
    //第三步操作,调用peek()方法获取栈顶元素位置
       obj = peek();
    //第四步操作,将栈顶的元素删除,就达到了pop()的功能
    //等下一起分析下peek()方法
       removeElementAt(len - 1);

       return obj;
   }
//第二步操作  
   public synchronized int size() {
       //这是一个线程安全的方法,返回集合元素的个数,成员变量elementCount
       return elementCount;
   }
//第四步操作
public synchronized void removeElementAt(int index) {
   //其实,这个不用太关心了
       modCount++;
   //首先,我们删除一个元素的时候,会先判断是否存在这个元素的
   //这里index=len-1就是数组空间的最后一个元素
       if (index >= elementCount) {
           throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                    elementCount);
       }
   //数组空间的起始位置是从0开始的,所以小于0,就需要抛出索引越界的问题
       else if (index < 0) {
           throw new ArrayIndexOutOfBoundsException(index);
       }
   //确定j的位置,便于数组元素的移动
       int j = elementCount - index - 1;
       if (j > 0) {
           System.arraycopy(elementData, index + 1, elementData, index, j);
       }
   //集合元素个数减一
       elementCount--;
   //将移除的元素置为null,和下面注释表达的一样的,就是为了触发gc来回收不可达对象的
   //以便整合内存空间
       elementData[elementCount] = null; /* to let gc do its work */
   }
   

2.5,peek()方法

public synchronized E peek() {
   //获取集合元素个数
       int     len = size();
 //集合个数长度为0时,再去获取元素时就应该抛出栈为空的异常
       if (len == 0)
           throw new EmptyStackException();
       return elementAt(len - 1);
   }
//第二步操作
public synchronized E elementAt(int index) {
   //校验索引是否越界
       if (index >= elementCount) {
           throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
       }
//根据索引下标位置获取指定位置的元素
       return elementData(index);
   }
//第三步操作
E elementData(int index) {
       return (E) elementData[index];
   }
   

2.6,isEmpty()方法

public boolean empty() {
    //判断集合size是否等于0
       return size() == 0;
   }
   

2.7,search()方法

public synchronized int search(Object o) {
       int i = lastIndexOf(o);

       if (i >= 0) {
           return size() - i;
       }
       return -1;
   }
//第二步操作
public synchronized int lastIndexOf(Object o) {
       return lastIndexOf(o, elementCount-1);
   }
//第三步操作
public synchronized int lastIndexOf(Object o, int index) {
   //预检查机制
       if (index >= elementCount)
           throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
//其实,集合是可以装填null元素的,所以这里需要区分,时间复杂度为O(n)
       if (o == null) {
           for (int i = index; i >= 0; i--)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = index; i >= 0; i--)
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }

感谢各位的阅读,以上就是“如何实现Stack栈”的内容了,经过本文的学习后,相信大家对如何实现Stack栈这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


文章名称:如何实现Stack栈
URL分享:http://cdxtjz.cn/article/igosge.html

其他资讯