栈的特点是先进后出,所以用数组实现栈时,只需要利用一个指针判定数据存储的位置即可,添加元素时判断指针是否超过数组长度,如果没有越界将元素添加到指针所指的位置,并将指针向下移动一位;否则返回异常,显示栈空间已满。删除元素思路类似,判断指针是否为数组初始位置,不是则将指针所指元素返回,并将指针向上。
public class ArrayStack {
private Integer[] arr;
private Integer index;
//初始化栈
public ArrayStack(int initSize) {
if(initSize < 0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
index = 0;
}
//返回栈顶元素
public Integer peek() {
if(index == 0) {
return null;
}
return arr[index - 1];
}
//入栈
public void push(int obj) {
if (index == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[index++] = obj;
}
//出栈
public Integer pop() {
if(index == 0){
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[--index];
}
}
队列的特点是先进先出"FIFO",所以用数组实现队列操作时,我们需要利用三个变量对数组进行操作,start指针用于记录先进队列的数据,end指针始终指向存入数据的下个位置,如果指针越界则返回0点。size用于记录队列中元素的个数,加入元素时需要先判断size大小是否超过数组的长度,如果超出则抛出异常显示队列已满,反之则将元素添加至end指针所指的位置,并将end指针移位(需要判断是否发生指针越界)。引用三个变量start、end、size能够让代码简单一点,更好理解。当队列未满时(cur_size<length),新加入的数放到end位置,当队列不为空时(size>0),出队的数为start位置的数。
public class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer start;
private Integer end;
//初始化队列大小
public ArrayQueue(int initSize){
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
start = 0;
end = 0;
}
//返回队顶元素
public Integer peek() {
if(size == 0) {
return null;
}
return arr[start];
}
//入队
public void push(int obj) {
if(size == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
arr[end] = obj;
end = (end == arr.length - 1)? 0 : end + 1;
}
//出队
public Integer poll() {
if(size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int tmp = start;
start = (start == arr.length - 1)? 0 : start + 1;
return arr[tmp];
}
}