栈的实现

栈的实现

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * 文件名：StackText.java
 * 时间：2014年10月21日下午8:43:02
 * 作者：修维康
 */
package chapter3;
/**
 * 类名：StackText 说明：用链表和数组分别实现栈；
 */
class ArrayStack<AnyType> {
	public static final int DEFAULT_CAPACITY = 10;
	private AnyType[] theArray;
	private int topOfStack;
	private int size;
	public ArrayStack() {
		clear();
		topOfStack = -1;
	}
	public void push(AnyType x) {
		if (size == theArray.length)
			ensureCapacity(2 * size + 1);
		theArray[++topOfStack] = x;
		size++;
	}
	public AnyType top() {
		if (topOfStack != -1)
			return theArray[topOfStack];
		return null;
	}
	public AnyType pop() {
		if (topOfStack != -1)
			size--;
		return theArray[topOfStack--];
	}
	public void clear() {
		topOfStack = -1;
		ensureCapacity(DEFAULT_CAPACITY);
	}
	public boolean isEmpty() {
		return topOfStack == -1;
	}
	public void ensureCapacity(int newCapacity) {
		if (newCapacity < size)
			return;
		AnyType[] old = theArray;
		theArray = (AnyType[]) new Object[newCapacity];
		for (int i = 0; i < size; i++)
			theArray[i] = old[i];
	}
}
/**
 * 类名：LinkedStack 说明：链表实现栈
 */
class LinkedStack<AnyType> {
	private static class Node<AnyType> {
		Node(AnyType data, Node<AnyType> prev) {
			this.data = data;
			this.prev = prev;
		}
		private AnyType data;
		private Node<AnyType> prev;
	}
	private Node<AnyType> bottom;
	public LinkedStack() {
		clear();
	}
	public void clear() {
		bottom = new Node<AnyType>(null, null);
	}
	public void push(AnyType x) {
		bottom = new Node<AnyType>(x, bottom);
	}
	public AnyType top() {
		if (bottom != null)
			return bottom.data;
		return null;
	}
	public AnyType pop() {
		if (bottom != null) {
			bottom = bottom.prev;
			return bottom.data;
		}
		return null;
	}
	public boolean isEmpty() {
		return bottom.prev == null;
	}
}
public class StackTest {
	/**
	 * 方法名：StackText.java 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayStack stack1 = new ArrayStack();
		for (int i = 1; i < 100; i++)
			stack1.push(i);
		// stack1.clear();
		System.out.println(stack1.top());
		while (!stack1.isEmpty())
			System.out.println(stack1.pop());
		ArrayStack stack2 = new ArrayStack();
		stack2.push(1);
		stack2.push(2);
		stack2.push(3);
		stack2.push(4);
		// stack2.clear();
		System.out.println(stack2.top());
		while (!stack2.isEmpty())
			System.out.println(stack2.pop());
	}
}