Java implementation stack for Java data structures
- 2020-04-01 03:08:11
- OfStack
import java.util.Arrays;
public class Stack<T> {
private int size; //The number of elements in the stack
private Object[] arr; //The underlying array
private final int defaultLength = 200; //The default length
public Stack(){
arr = new Object[defaultLength];
size = 0;
}
public Stack(int length){
arr = new Object[length];
size = 0;
}
public void push(T element){
//Do we need to expand capacity
if(size >= arr.length){
//Array capacity
extendCapacity(size+1);
}
arr[size++] = element;
}
@SuppressWarnings("unchecked")
public T pop(){
//The number of elements is 0. The stack operation cannot be performed
if(size==0){
return null;
}
T t = (T)arr[size-1];
arr[--size] = null; //The data has been pushed out of the stack and restored to null
return t;
}
public void clear(){
for(int i=0;i<size;i++){
arr[i]=null;
}
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
@SuppressWarnings("unchecked")
public void printStack(){
for(int i=0;i<size;i++){
System.out.print(((T)arr[i]).toString());
}
System.out.println();
}
private void extendCapacity(int length){
//The current array length and the required length are maximized
int minCapacity = Math.max(arr.length, length);
// judge Do we need to expand capacity
if(minCapacity - arr.length>0){
//The array length is increased by half
int newLength = arr.length + arr.length/2;
//If the new length is smaller than the requirement, use the length of the requirement as the array length
if(newLength < minCapacity){
newLength=minCapacity;
}
//The array length cannot exceed integer.max_value
if(newLength > Integer.MAX_VALUE - 8){
newLength = Integer.MAX_VALUE;
}
//Array capacity
arr = Arrays.copyOf(arr, newLength);
}
}
}