Stack这个数据结构还是比较容易理解的,满足LIFO,即先进后出,看下它的结构图,然后分析一下源码进行理解一下。
咦,Stack栈继承Vector类,然后复用了其中的方法,就实现了栈这种push(),pop()方法的使用,优秀。
看下栈Stack的类结构,确实是继承了Vector这个类。
public class Stack<E> extends Vector<E> {}
首先看下,如何创建一个栈Stack,默认提供了一个无参构造函数。
/** * Creates an empty Stack. */ public Stack() {//构建一个空参 }
将数据元素放入栈中,其实是放入了动态数组中,底层调用了Vector类的方法。
public E push(E item) { addElement(item);
return item; } 步骤一:public synchronized void addElement(E obj) {//这个讲解见Vector源码分析 modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; }
我们看下如何在不弹出栈中元素数据的情况下,如何获取栈顶元素。可以使用peek()方法。
public synchronized E peek() { int len = size();//获取当前栈中元素个数
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);//获取指定索引位置的元素 }
看下Stack中弹出栈顶元素pop()方法,size减一。
public synchronized E pop() { E obj; int len = size();
obj = peek(); removeElementAt(len - 1);//这里是移除指定位置的元素方法
return obj; } 步骤一: 删除指定位置元素为null,使用gc进行null值数据的垃圾收集,但是垃圾收集时间不确定 public synchronized void removeElementAt(int index) { modCount++; if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } int j = elementCount - index - 1; if (j > 0) { System.arraycopy(elementData, index + 1, elementData, index, j); } elementCount--; elementData[elementCount] = null; /* to let gc do its work */ }
这也就是peek()和pop()方法的区别。
获取栈Stack中元素个数的方法:size()。
public synchronized int size() { return elementCount;//复用了vector容器获取size方法。 }
判断栈Stack是否为空的方法:isEmpty()。
public synchronized boolean isEmpty() { return elementCount == 0;//也是复用了vector元素个数与0的对比。 }
判断指定元素是否在栈Stack中存在search()方法。
public synchronized int search(Object o) { int i = lastIndexOf(o);//获取指定元素的下标位置,由于栈是先进后出的结构,所以这里使用了lastIndexOf()
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);
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这种LIFO结构的源码进行解析和理解,到这里就结束了,关于源码走读的示例程序,这里自己也简单的提供一下。
package com.wpw.springbootjuc.java8.map;
import lombok.extern.slf4j.Slf4j;
import java.util.Stack;
/** * 栈源码走读 * * @author wpw */@Slf4jpublic class StackTest { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); log.info("循环输出栈中的元素"); stack.stream().forEachOrdered(item -> System.out.print(item + "\t")); System.out.println(); log.info("Stack中peek()方法的测试"); Integer item = stack.peek(); System.out.println("item = " + item); log.info("获取栈中元素个数:[{}]", stack.size()); System.out.println(); log.info("Stack中pop()方法的测试"); Integer itemPop = stack.pop(); System.out.println("itemPop = " + itemPop); log.info("获取栈中元素个数:[{}]", stack.size()); System.out.println(); log.info("判断Stack是否为空:{}", stack.isEmpty()); log.info("查找指定元素是否在Stack中存在:[{}]", stack.search(3)); }}
理解Vector源码是进一步理解栈这种结构的前面铺垫,关于Vector源码解析的文章可以参考历史文章。这里贴下Stack的结构方法。