数据结构(三)| 用数组实现队列和栈

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

锲而舍之,朽木不折;锲而不舍,金石可镂。

---荀子《劝学》

在上一篇文章 数据结构(二)| 队列与栈 中,我用双向链表实现了队列和栈,本文用数组来实现。

用数组实现栈

由于栈的逻辑结构是先进后出后进去的先出来,图解如下:

数据结构(三)| 用数组实现队列和栈
用数组实现栈

从图解看出,用数组实现栈时比较简单,只需要维护index的值防止数组越界即可,代码实现:

public class MyStack {
    private int[] array;
    private int index;
    
    public MyStack(int size) {
        this.array = new int[size];
    }
    
    //入栈
    public void push(int value) {
        if (index >= array.length) {
            throw new RuntimeException("栈满,不让加了");
        }
        array[index++] = value;
    }
    
    //出栈
    public int pop() {
        if (index <= 0) {
            throw new RuntimeException("栈空,不能取出");
        }
        return array[--index];
    }
}

用数组实现队列

我们再来图解分析一下,如何用数组实现队列。

入队列,依次加入1,2,3,4,5:

数据结构(三)| 用数组实现队列和栈

队列达到给定数组的长度个元素后,下面来分析一下从队列取出数据、再添加数据的过程:

数据结构(三)| 用数组实现队列和栈

要符合队列的先进先出特性,这个数组就像一个循环数组,当队列满(指队列元素个数达到指定数组长度)了,取出元素,再继续添加元素的时候,index又来到了开始的位置,如此往复。

现在我们假设两个指针,begin和end,再增加一个变量size来表示队列当前元素个数。

当size大于指定数组长度时,就不能往队列里插入数据了;当size<0时,就不能从队列取数据了——也就是说用这个size变量来控制能否push和pop。

当要插入数据时,将要插入的数据放到end的位置,然后让end++,此时需要注意下标越界的问题,若end大于等于size了,就需要将end设置到0的位置了,图解如下:

数据结构(三)| 用数组实现队列和栈
插入数据

当要取出数据时,因为队列的先进先出特点,最先进入到队列的数据在begin位置,所以从begin位置取数,同时让begin++,来到新的最早进入队列的数据位置,同理也要注意begin的下标是否越界。如下图所示:

数据结构(三)| 用数组实现队列和栈
利用begin和end指针操作队列

从上面的分析可知,插入数据和取出数据用size和begin、end指针就可以完成。

用数组实现队列的代码如下:

public static class MyQueue {
    private int[] array;
    private int begin;
    private int end;
    private int size;

    public MyQueue (int limit) {
        this.array = new int[limit];
        this.begin = 0;
        this.end = 0;
        this.size = 0;
    }

    public void push (int value) {
        size++;
        if (size > array.length) {
            throw new RuntimeException("队列满了");
        }
        array[end] = value;
        end++;
        //针对end越界的处理
        if (end >= array.length) {
            end = 0;
        }
    }

    public int pop () {
        size--;
        if (size < 0) {
            throw new RuntimeException("队列已空");
        }
        int result = array[begin];
        begin++;
        //针对begin越界的处理
        if (begin >= array.length) {
            begin = 0;
        }
        return result;
    }
}

小结

用数组实现有技巧,需要根据size来控制是否能插入取出,然后借助辅助指针来移动并记录数组下标。

仍然建议画图加深理解。


原文始发于微信公众号(行百里er):数据结构(三)| 用数组实现队列和栈