-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBetterStack.java
More file actions
164 lines (143 loc) · 4.45 KB
/
BetterStack.java
File metadata and controls
164 lines (143 loc) · 4.45 KB
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
package CommonUtils;
import java.util.Arrays;
import java.util.EmptyStackException;
/**
* @implNote Implement a stack using an array with initial capacity 8.
*
* Implement BetterStackInterface and add a constructor
*
* You are explicitly forbidden from using java.util.Stack and any
* other java.util.* library EXCEPT java.util.EmptyStackException and java.util.Arrays.
* Write your own implementation of a Stack.
*
*
* @param <E> the type of object this stack will be holding
*/
public class BetterStack<E> implements BetterStackInterface<E> {
/**
* Initial size of stack. Do not decrease capacity below this value.
*/
private static final int INIT_CAPACITY = 8;
/**
* If the array needs to increase in size, it should be increased to
* old capacity * INCREASE_FACTOR.
*
* If it cannot increase by that much (old capacity * INCREASE_FACTOR > max int),
* it should increase by CONSTANT_INCREMENT.
*
* If that can't be done either throw OutOfMemoryError()
*
*/
private static final int INCREASE_FACTOR = 2;
private static final int CONSTANT_INCREMENT = 1 << 5; // 32
/**
* If the number of elements stored is < capacity * DECREASE_FACTOR, it should decrease
* the capacity of the UDS to max(capacity * DECREASE_FACTOR, initial capacity).
*
*/
private static final double DECREASE_FACTOR = 0.5;
/**
* Array to store elements in (according to the implementation
* note in the class header comment).
*/
private E[] stack;
private int capacity;
private int size;
/**
* Constructs an empty stack
*/
@SuppressWarnings("unchecked")
public BetterStack() {
this.stack = (E[]) new Object[INIT_CAPACITY];
this.capacity = INIT_CAPACITY;
this.size = 0;
}
/**
* Push an item onto the top of the stack
*
* @param item item to push
* @throws OutOfMemoryError if the underlying data structure cannot hold any more elements
*/
@Override
public void push(E item) throws OutOfMemoryError {
stack[size++] = item;
if (size < capacity) return;
// Resize array if size exceeds capacity
int newCapacity = capacity;
if (capacity <= Integer.MAX_VALUE / INCREASE_FACTOR)
newCapacity *= INCREASE_FACTOR;
else if (capacity <= Integer.MAX_VALUE - CONSTANT_INCREMENT)
newCapacity += CONSTANT_INCREMENT;
else
throw new OutOfMemoryError();
resize(newCapacity);
}
private void resize(int newCapacity) {
E[] newStack = (E[]) new Object[newCapacity];
System.arraycopy(stack, 0, newStack, 0, size);
this.stack = newStack;
this.capacity = newCapacity;
}
/**
* Remove and return the top item on the stack
*
* @return the top of the stack
* @throws EmptyStackException if stack is empty
*/
@Override
public E pop() {
if (size == 0) throw new EmptyStackException();
E res = stack[--size];
// Decrease buffer size if not utilizing all of it
int decreaseThresh = (int) Math.max(INIT_CAPACITY, capacity * DECREASE_FACTOR);
if (size < decreaseThresh) {
resize(decreaseThresh);
}
return res;
}
/**
* Returns the top of the stack (does not remove it).
*
* @return the top of the stack
* @throws EmptyStackException if stack is empty
*/
@Override
public E peek() {
if (size == 0) throw new EmptyStackException();
return stack[size - 1];
}
/**
* Returns whether the stack is empty
*
* @return true if the stack is empty, false otherwise
*/
@Override
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns the number of elements in the stack
*
* @return integer representing the number of elements in the stack
*/
@Override
public int size() {
return size;
}
@Override
public String toString() {
return Arrays.toString(stack);
}
/**
* DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
*
* @param g graphics object to draw on
*/
@Override
public void draw(java.awt.Graphics g) {
//DO NOT MODIFY NOR IMPLEMENT THIS FUNCTION
if(g != null) g.getColor();
//todo GRAPHICS DEVELOPER:: draw the stack how we discussed
//251 STUDENTS:: YOU ARE NOT THE GRAPHICS DEVELOPER!
}
}