1.栈 List
定义
栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。
栈有时又叫做LIFO（后进先出）表，即last-in，first-out
现实中的栈
栈的接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public
interface
StackInterface<T> {
/**
* 将新元素加到站定
* @param newEntry 带插入站的对象 */
public
void
push(T newEntry);
/**
* 删除并返回栈顶
* @return 栈顶的对象，如果栈为空则返回null */
public
T pop();
/**
* 取出栈顶
* @return 栈顶的对象，如果栈为空则返回null */
public
T peek();
/**
* 检查栈是否为空
* @return 如果栈为空返回true */
public
boolean
isEmpty();
/**
* 从栈中删除所有元素 */
public
void
clear();
}
|
程序栈
当一个程序执行时，一个被称为程序计数器的专用存储单元指向当前指令。当一个方法被调用时，程序的运行时环境为这个方法创建一个称为活动记录或栈帧的对象，这个活动记录显示该方法在执行过程中的状态。具体说，活动记录含有方法的实参、局部变量和当前指令的引用，即程序计数器的一个副本。在这个方法被调用时，活动记录被压入称为程序栈（或者称为Java栈）中。
由于一个方法可以调用另一个方法，程序栈往往含有多个活动记录。位于栈顶的活动记录，属于当前正在执行的方法，紧接在栈顶下的记录，属于调用当前方法的方法。
当main开始执行，他的活动记录位于程序栈顶，如图A
当main调用methodA时，一个新的记录被压入栈，此时程序计数器为50，图B展示methodA刚开始执行时，main更新记录与methodA的新纪录
当methodA调用methodB时，程序计数器为120，一个新的活动记录被压入栈。图C展示当methodB刚开始执行时main为改变的记录、methodA更新后的记录以及methodB的新纪录。
在methodB执行过程中，活动记录被更新，但main和methodA的记录保持不变。
Java类库：类Stack
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public
class
Stack<T> {
public
T push(T item);
public
T pop();
public
T peek();
public
boolean
empty();
/**
* 在栈中查找指定对象
* @param desiredItem 待查找的对象
* @return 如果desiredItem在栈中，则返回其位置；如果不在则返回-1；栈顶的位置是-1 */
public
int
search(T desiredItem);
/**
* @return 栈的一个遵循Java接口的Iterator的迭代器 */
public
Iterator<T> iteraotr();
/**
* @return 栈的一个遵循Java接口ListIterator的迭代器 */
public
ListIterator<T> listIterator();
}
|
2.基于链表的实现
如果用链表表示栈，则第一个结点应该引用栈顶元素。
类的框架
栈的链表实现有一个数据域topNode，它是链表的表头引用，默认构造函数将这个数据域设置为null。
|
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
|
public
class
LinkedStack<T>
implements
StackInterface<T>, Serializable {
private
Node topNode;
//引用链表中第一个结点
public
LinkedStack() {
topNode =
null
;
}
private
class
Node
implements
Serializable {
private
T data;
//栈的元素
private
Node next;
//指向下一个结点的连接
}
// 在栈顶插入
public
void
push(T newEntry) {
Node newNode =
new
Node(newEntry, topNode);
topNode = newNode;
}
// 删除栈顶
public
T pop() {
T top =
null
;
if
(topNode !=
null
) {
top = topNode.getData();
topNode = topNode.getNext();
}
return
top;
}
// 检索栈顶
public
T peek() {
T top =
null
;
if
(topNode !=
null
)
top = topNode.getData();
return
top;
}
public
boolean
isEmpty() {
return
topNode ==
null
;
}
public
void
clear() {
topNode =
null
;
}
}
|
3.基于数组的实现
|
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
|
public
class
ArrayStack<T>
implements
StackInterface<T>, Serializable {
private
T[] stack;
//存放栈元素的数组
private
int
topIndex;
// 栈顶元素索引
private
static
final
int
DEFAULT_MAX_SIZE =
50
;
public
ArrayStack() {
this
(DEFAULT_MAX_SIZE);
}
public
ArrayStack(
int
initialCapacity) {
stack = (T[])
new
Object[initialCapacity];
topIndex = -
1
;
}
// 在栈顶插入
public
void
push(T newEntry) {
topIndex++;
if
(topIndex >= stack.length) {
//若数组已满，扩展数组
}
stack[topIndex] = newEntry;
}
// 删除栈顶
public
T pop() {
T top =
null
;
if
(!isEmpty()) {
top = stack[topIndex];
stack[topIndex] =
null
;
topIndex--;
}
return
top;
}
// 检索栈顶
public
T peek() {
T top =
null
;
if
(!isEmpty())
top = stack[topIndex];
return
top;
}
public
boolean
isEmpty() {
return
topIndex <
0
;
}
public
void
clear() {
stack =
null
;
}
}
|
4.基于向量的实现
|
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
|
public
class
VectorStack<T>
implements
StackInterface<T>, Serializable {
private
Vector<T> stack;
//栈顶是最后一个元素
public
VectorStack() {
stack =
new
Vector();
// 需要时向变量大小将成倍增加
}
public
VectorStack(
int
maxSize) {
stack =
new
Vector(maxSize);
}
// 在栈顶插入
public
void
push(T newEntry) {
stack.addElement(newEntry);
}
// 删除栈顶
public
T pop() {
T top =
null
;
if
(!isEmpty()) {
top = stack.lastElement();
stack.removeElement(stack.size() -
1
);
}
return
top;
}
// 检索栈顶
public
T peek() {
T top =
null
;
if
(!isEmpty())
top = stack.lastElement();
return
top;
}
public
boolean
isEmpty() {
return
stack.isEmpty();
}
public
void
clear() {
stack.removeAllElements();
}
}
|
本文转自 LinkedKeeper 51CTO博客，原文链接：http://blog.51cto.com/sauron/1225873，如需转载请自行联系原作者
