java中的数据结构之集合框架源码分析的系列文章如下:
JAVA集合框架源码分析1-ArrayList
JAVA集合框架源码分析2-Stack
JAVA集合框架源码分析3-LinkedList
Stack(栈),实际使用的我感觉也不是很多,但是作为一个典型的顺序表的数据结构,还是简单分析下吧,说简单分析下,是因为它包含的方法也并不是很多。
1.继承关系
public class Stack<E> extends Vector<E>
直接继承了Vector
2.构造方法
只有一个默认的构造方法
public Stack() {
}
3.操作——增加
public E push(E item) {
addElement(item);
return item;
}
调用了父类的addElement,
//同步方法,确保了线程安全
public synchronized void addElement(E obj) {
modCount++;
//确定是否需要进行扩容,elementCount 是数组存储结构,与ArrayList是一样的存储结构
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//进行扩容操作
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
4.操作——删除
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
//调用父类的方法
removeElementAt(len - 1);
return obj;
}
//同步方法,实现了线程安全
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) {
//将elementData的元素从index+1开始的j个元素依次放置到从elementData的index起始位置
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
5.操作——查找
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);
}
6.总结
Stacke的实现也是顺序表结构
网友评论