Fork me on GitHub

Java Stack类简介

前言

栈(Stack)是限定只能在一段进行插入和删除操作的线性表。

进行插入和删除操作的一端称为“栈顶”(top),另一端称为“栈底”(bottom)。

栈的插入操作称为“入栈”(push),栈的删除 操作称为“出栈”(pop)。

栈具有后进先出(LIFO),先进后出(FILO)的特性。

Stack类

Java工具包下的Stack类继承于Vector,由此可见Stack底层是由数组实现的。

Stack和Collection的关系如下图:

upload successful

我们来看下Stack的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package java.util;

public
class Stack<E> extends Vector<E> {
/**
* 构造函数
*/
public Stack() {
}

/**
* 将一个元素压入栈顶
*/
public E push(E item) {
addElement(item);

return item;
}

/**
* 取出栈顶的一个元素,并删除
*/
public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len - 1);

return obj;
}

/**
* 取出栈顶元素,不删除
*/
public synchronized E peek() {
int len = size();

if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}

/**
* 判断栈是不是空
*/
public boolean empty() {
return size() == 0;
}

/**
* 查找元素在栈的位置,没有返回-1
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);

if (i >= 0) {
return size() - i;
}
return -1;
}

private static final long serialVersionUID = 1224463164541339165L;
}

根据源码,可以发现Stack的方法调用了Vector类的方法,实现了线程安全。

我们主要看一下Vector里的下面三个方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//添加一个元素
public synchronized void addElement(E obj) {
modCount++;
//确认容量,不够会扩容
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = 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) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
//赋空,便于垃圾回收
elementData[elementCount] = null;
}

//找出在指定位置的元素
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}

return elementData(index);
}

关联方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//
private void ensureCapacityHelper(int minCapacity) {
如果长度超了就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//新的容量定义:如果有容量增量且大于0,取增量,否则执行2倍扩容
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)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

实践

我们如何用数组实现自己的一个stack呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Stack {
//栈元素组
private Object[] members;
//指针
private int size;
//自定义初始栈长度
public Stack(int initCapacity) throws Exception{
if(initCapacity<=0) {
throw new Exception();
}
this.members=new Object[initCapacity];
}
//默认栈长度为10
public Stack() {
this.members=new Object[10];
}

//元素入栈
public synchronized void push(Object o){
ensureCapacity(size+1);
members[size++]=o;
}

//元素出栈
public synchronized Object pop() throws Exception{
if(size<=0) {
throw new Exception();
}
return members[--size];
}
//查看栈顶元素
public synchronized Object peek() throws Exception{
if(size<=0) {
throw new Exception();
}
return members[size-1];
}


//确认容量
private synchronized void ensureCapacity(int minCapacity) {
//size+1比数组长度要长,扩容
if(minCapacity-members.length>0) {
int oldCapacity = members.length;
Object oldMembers=members;
//扩容到二倍
int newCapacity = 2 * oldCapacity ;
//扩容后还不够或者超过int最大值,就直接赋值size+1
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
members=new Object[newCapacity];
//拷贝数组
System.arraycopy(oldMembers, 0, members, 0, size);
oldMembers=null;
}
}
}

以上代码就是一个简易的Stack的实现方式。

代码见: https://github.com/JavaZWT/sakuratears

总结

Stack类在编程过程中用到的不是很多,但是计算机栈内存机制遵循先进后出原则,学习Stack类,可以帮助我们加深对程序及数据结构的理解。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%