用数组结构实现大小固定的队列和栈
固定数组实现栈
思路:维护一个index即可,index表示如果新加一个数,这个数应该加在哪个位置,index<size
具体代码如下:
public static class ArrayStack { private Integer[] arr; private Integer size; public ArrayStack(int initSize) { if (initSize < 0) { throw new IllegalArgumentException("The init size is less than 0"); } arr = new Integer[initSize]; size = 0; } //peek方法的意思是,返回栈顶元素,但是栈顶元素保留 public Integer peek() { if (size == 0) { return null; } return arr[size - 1]; } public void push(int obj) { if (size == arr.length) { throw new ArrayIndexOutOfBoundsException("The queue is full"); } //size位置填上,再size++ arr[size++] = obj; } //将index-1位置返回给用户,再index-- public Integer pop() { if (size == 0) { throw new ArrayIndexOutOfBoundsException("The queue is empty"); } return arr[--size]; } }
固定数组实现队列
准备俩个变量,一个是end代表如果新加一个数,这个数应该填到哪,初始值为0,一个是start,表示如果获取一个数,从哪个位置开始获取。start初始值0,通过设置size约束start和end的行为。
具体代码如下:
public static class ArrayQueue { private Integer[] arr; private Integer size; private Integer first; private Integer last; public ArrayQueue(int initSize) { if (initSize < 0) { throw new IllegalArgumentException("The init size is less than 0"); } arr = new Integer[initSize]; size = 0; first = 0; last = 0; } public Integer peek() { if (size == 0) { return null; } return arr[first]; } public void push(int obj) { if (size == arr.length) { throw new ArrayIndexOutOfBoundsException("The queue is full"); } size++; arr[last] = obj; //如果last来到最后一个位置,跳回到0位置,如果没有来到最后一个位置,last++ last = last == arr.length - 1 ? 0 : last + 1; } public Integer poll() { if (size == 0) { throw new ArrayIndexOutOfBoundsException("The queue is empty"); } size--; int tmp = first; //如果start来到最后一个位置,跳回到0位置,如果没有来到最后一个位置,start++ first = first == arr.length - 1 ? 0 : first + 1; return arr[tmp]; } }