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

发表于 2019-03-26 更新于 2022-09-13 阅读次数：

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

使用数组实现栈

核心思想

使用一个数组和一个size变量，通过size和0还有array.length的关系控制边界条件。size指向数组中存储的最后一个元素的下一个位置，同时也正是数组的size。

peek()和pop()就返回数组最后一个元素

代码

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

    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");
        }
        arr[size++] = obj;
    }

    public Integer pop() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        return arr[--size];
    }
}

使用数组实现队列

核心思想

使用一个数组和三个额外的变量，一个size，一个first，保存队列头元素的索引，一个last，保存队列尾元素的索引。如果first或者last走到最后一个元素了，那么就修改其值为0，相当于从头开始。

代码

public 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 = (last == arr.length - 1) ? 0 : last + 1;
    }

    public Integer poll() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        size--;
        int firstCopy = this.first;
        this.first = (this.first == arr.length - 1) ? 0 : this.first + 1;
        return arr[firstCopy];
    }
}

0%