使用数组实现栈

1
2
3
4
自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()
这些基本的方法。

提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容；
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

package program;

import java.util.Arrays;

public class MyStack {

	/*
	 * 使用数组实现栈： 自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek()
	 * （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。
	 * 提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容；
	 */

	/*
	 * 存数据的数组
	 */
	private int[] storage;

	/*
	 * 容量
	 */
	private int capacity;

	/*
	 * 元素个数
	 */
	private int count;

	/*
	 * 每次以当前容量进行扩容
	 */
	private static final int GROW_FACTOR = 2;

	// TODO：默认构造函数
	public MyStack() {
		this.capacity = 8;
		this.count = 0;
		this.storage = new int[8];
	}

	// TODO：带初始容量的构造方法
	public MyStack(int initialCapacity) {
		if (initialCapacity < 1)
			throw new IllegalArgumentException("Capacity too small.");

		this.capacity = initialCapacity;
		this.storage = new int[initialCapacity];
		this.count = 0;
	}

	// TODO： 入栈
	public void push(int value) {
		if (count == capacity) {
			scrollUpCapacity();
		}
		storage[count++] = value;		
	}

	// TODO: 扩容
	private void scrollUpCapacity() {
		int newCapacity = capacity * GROW_FACTOR;
		storage = Arrays.copyOf(storage, newCapacity);
		capacity = newCapacity;
	}

	// TODO： 返回栈顶元素(出栈)
	public int pop() {
		count--;
		if (count == -1) {
			throw new IllegalArgumentException("Stack is empty.");
		}
		return storage[count];
	}

	// TODO： 返回栈顶元素(不出栈)
	public int peek() {
		if (count == 0) {
			throw new IllegalArgumentException("Stack is empty.");
		} else {
			return storage[count - 1];
		}
	}

	// TODO: 判断是否为空
	public boolean isEmpty() {
		return count == 0;
	}

	// TODO: 返回长度(元素个数)
	public int size() {
		return count;
	}

	public static void main(String[] args) {
		MyStack myStack = new MyStack(3);
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		myStack.push(4);
		myStack.push(5);
		myStack.push(6);
		myStack.push(7);
		myStack.push(8);
		System.out.println(myStack.peek());// 8
		System.out.println(myStack.size());// 8
		for (int i = 0; i < 8; i++) {
			System.out.println(myStack.pop());
		}
		System.out.println(myStack.isEmpty());// true
		myStack.pop();// 报错：java.lang.IllegalArgumentException: Stack is empty.

		myStack.push(520);
	}

}