栈的特点

  • 一段连续的内存空间
  • 先进后出
  • push（进栈）、pop（出栈）

实现

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
package stack;
import java.util.Arrays;
/**
 * 栈的定义
 *
 * @author jack
 * 2016-11-18 上午12:56:22
 */
public class Stack {
	
	private int cap = 10;   // 数组长度
	
	private int size = 0;   // 已经使用长度
	private Object[] arr;	// 存储
	// 构造器
	public Stack(int cap) {
		super();
		this.cap = cap;
		arr = new Object[cap];
	}
	// 入栈，考虑扩容
	public boolean push(Object object) {
		// 扩容
		if (isFull()) {
			expand();
		}
		//添加元素
		arr[size ++] = object;
		return true;
	}
	
	// 出栈
	public Object pop() throws Exception{
		if(isEmpty()){
			throw new Exception("No ele in this stack");
		}
		Object result = getTop();
		size-- ;
		return result;
	}
	
	// 栈顶元素
	public Object getTop(){
		return arr[size - 1];
	}
	
	// 判断是否满
	public boolean isFull() {
		return size == cap;
	}
	// 判断是否空
	public boolean isEmpty() {
		return size == 0;
	}
    // 扩容
	private void expand() {
		cap = cap * 2;
		arr = Arrays.copyOf(arr, cap);
	}
}
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
package stack;
/**
 * @author jack
 * 2016-11-18 上午1:08:53
 */
public class Test {
	public static void main(String[] args) {
		Stack stack = new Stack(5);
		
		for (int i = 0; i < 15; i++) {
			stack.push(i + "");
		}
		for (int i = 0; i < 15; i++) {
			try {
				System.out.println(stack.pop());
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		try {
			System.out.println(stack.pop());
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

使用场景

  • 逆序输出。
  • 语法检查：凡是遇到“（”则入栈，只要遇到“）”就对比栈顶元素是否与之对应。
  • 数制转换。

数制转换：

1
2
3
4
5
6
题目：十进制100转换为8进制
解法：  将 100 ➗ 8 = 12 余 4，将4压入栈。
        将 12 ➗ 8  = 1 余 4 ,  将4压入栈 。
        1 压入栈
        出栈：144
结果：  144