专栏首页JavaJourney数据结构(三)| 用数组实现队列和栈

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

锲而舍之,朽木不折;锲而不舍,金石可镂。 ---荀子《劝学》

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

用数组实现栈

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

用数组实现栈

从图解看出,用数组实现栈时比较简单,只需要维护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

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:行百里er
原始发表时间:2021-06-16
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 数据结构|数组,栈和队列[1]

    数组的大小固定,如果存储数量过多,需要重建新数组;同时存储的数据类型单一,每个元素占用内存大小相同;添加,删除,移动操作比较慢,因为需要改变受影响的元素

    rare0502
  • 数组实现栈和队列

    我们需要设置一个数组当作栈,一个index当作栈指针 当我们往数组中添加数据时候,栈指针+1 当我们栈指针指向size时候,再要求加数据要报错 当我们往数...

    名字是乱打的
  • 数据结构设计:用栈实现队列/用队列实现栈

    这两种数据结构底层其实都是数组或者链表实现的,只是 API 限定了它们的特性,那么今天就来看看如何使用「栈」的特性来实现一个「队列」,如何用「队列」实现一个「栈...

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

    大学里的混子
  • [算法题] 使用数组实现栈和队列

    CoderJed
  • 数据结构(三)-- 栈、队列

    栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作...

    看、未来
  • 用栈实现队列

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push、pop、peek、empty):

    _kyle
  • 用栈实现队列

    一份执着✘
  • [随缘一题]用栈实现队列

    队列应支持push(element),pop() 和 top(),其中pop是弹出队列中的第一个(最前面的)元素。

    呼延十
  • 用队列实现栈

    你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。...

    _kyle
  • [第 3 期]JavaScript数据结构之数组栈队列

    桃翁
  • 数据结构 - 栈和队列

    栈(stack) 是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。表尾的一端有其特殊含义,称为 栈顶(top) ,相应地,表头称为 ...

    忆想不到的晖
  • 用数组和链表实现单向队列

    前面我们学习了链表的相关知识,今天我们接着来学习另外一种数据结构-----》队列。其实,不管是数组还是链表,都是属于线性表,那么什么是线性表呢?线性表是具有相同...

    码农飞哥
  • 数据结构(三):栈与队列

    3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: ? (1) 如果进站的车厢序列为123,则可能...

    云时之间
  • 数据结构-栈和队列

    栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:

    黄规速
  • 数据结构-栈和队列

    我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

    张俊红
  • 栈与队列:用队列实现栈还有点别扭

    刚刚做过栈与队列:我用栈来实现队列怎么样?的同学可能依然想着用一个输入队列,一个输出队列,就可以模拟栈的功能,仔细想一下还真不行!

    代码随想录
  • 使用数组模拟队列、循环队列和栈

    在一些考试题中以及笔试面试的过程中,在需要使用stack和queue的时候,可能被要求不能使用STL中相关的库函数,也就意味着我们需要使用纯C进行编程。但是如果...

    lexingsen
  • 数据结构:数组、链表、栈、队列的理解

    解释定义 数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。 如果还是不太清楚下面会...

    纪莫

扫码关注腾讯云开发者

领取腾讯云代金券