用数组结构实现大小固定的队列和栈（java）

用户5513909

发布于 2023-04-25 03:29:26

93700

代码可运行

文章被收录于专栏：小鱼儿我的学习笔记小鱼儿我的学习笔记

运行总次数：0

代码可运行

栈的实现

栈的特点是先进后出，所以用数组实现栈时，只需要利用一个指针判定数据存储的位置即可，添加元素时判断指针是否超过数组长度，如果没有越界将元素添加到指针所指的位置，并将指针向下移动一位；否则返回异常，显示栈空间已满。删除元素思路类似，判断指针是否为数组初始位置，不是则将指针所指元素返回，并将指针向上。

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];
    }
}