专栏首页Jed的技术阶梯[算法题] 使用数组实现栈和队列

[算法题] 使用数组实现栈和队列

1. 使用数组实现栈

public class ArrayToStack {

    public static class ArrayStack{

        private Integer[] arr;  // 使用数组表示栈这个容器
        private Integer index;  // 使用index表示栈当前可以存放元素的下标

        public ArrayStack(Integer initSize) {
            if(initSize < 0) {
                throw new IllegalArgumentException("stack's size should > 0");
            }
            arr = new Integer[initSize];
            index = 0;
        }

        // peek(): 只返回栈顶的值,而不弹出栈顶的元素
        public Integer peek() {
            if(index == 0) {
                return null;
            }
            return arr[index - 1];
        }

        // push(): 压栈
        public void push(Integer element) {
            if(index == arr.length) {
                throw new ArrayIndexOutOfBoundsException("This stack is full!");
            }
            // 先给index下标处赋值,然后index+1
            arr[index++] = element;
        }

        // pop(): 弹栈
        public Integer pop() {
            if(index == 0) {
                throw new ArrayIndexOutOfBoundsException("This stack is empty!");
            }
            return arr[--index];
        }

    }

}

2. 使用数组实现队列

public class ArrayToQueue {

    public static class ArrayQueue {

        private Integer[] arr;  // 使用数组表示一个队列
        private Integer size;   // size表示队列中元素的个数
        private Integer start;  // start表示从队列中取数的索引
        private Integer end;    // end表示从队列中放数的索引
        // start被size约束,end被size约束,但start和end没有关系,一个只管取数,一个只管放数

        public ArrayQueue(int initSize) {
            if(initSize < 0) {
                throw new IllegalArgumentException("queue's size should > 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 element) {
            if(size == arr.length) {
                throw new ArrayIndexOutOfBoundsException("This queue is full!");
            }
            size++;
            arr[end] = element;
            // 如果当前元素是放到数组的最后一个位置处,那么把end置为0,表示下次放数的时候从数组第一个位置开始放
            end = (end == arr.length - 1 ? 0 : end + 1);
        }

        public Integer poll() {
            if(size == 0) {
                throw new ArrayIndexOutOfBoundsException("This queue is empty!");
            }
            size--;
            int tmp = start;
            start = (start == arr.length - 1 ? 0 : start + 1);
            return arr[tmp];
        }

    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 021.Elasticsearch索引管理高级篇

    在开发中,随着业务需求的迭代,较老的业务逻辑就要面临更新甚至是重构,而对于ES来说,为了适应新的业务逻辑,可能就要对原有的索引做一些修改,比如对某些字段做调整,...

    CoderJed
  • Hive案例03-最高气温

    现有hive表temp,其中只有一个字段(temp_record string),每一行代表某一天的气温,比如,2014010114代表,2014年1月1日的气...

    CoderJed
  • zookeeper编程02-服务器上下线动态感知

    NameNode判断DataNode是否下线的时间太长了,利用zookeeper实现服务器上下线动态感知

    CoderJed
  • 封装数组之改进为泛型数组

    前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组...

    wfaceboss
  • 看得见的数据结构Android版之表的数组实现(数据结构篇)

    张风捷特烈
  • 算法学习之动态数组类

    让我们的数据结构可以放置“任何”数据类型 不可以是基本数据类型,只能是类对象 boolean,byte , char,short,int,long,floa...

    慕白
  • 搞定数据结构-数组结构

    从数组存储的内存模型来看,“下标”最确切的定义应该是”偏移”,如果用a来表示数组的首地址,a0 就是偏移为0的位置,也就是首地址,a k就表示偏移k个type_...

    用户3045442
  • tensorflow自定义op:work_shard

    强行解释 work_shard 在学习 tensorflow 自定义 op 的时候碰到的,google 了一下,也没有找到详细的介绍,难道是姿势不对?? ...

    ke1th
  • 数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解

    对数组有不了解的可以先看看我的另一篇文章,那篇文章对数组有很多详细的解析,而本篇文章则着重讲动态数组,另一篇文章链接如下,可点击跳转: 链接:https://...

    一只胡说八道的猴子
  • 封装数组之实现在数组中查询元素和修改元素

    前言:在上一小节中,我们已经对如何往数组中添加一个元素的方法进行了编写,此节中我们就如何查询出数组中元素与修改元素的方法进行编写。

    wfaceboss

扫码关注云+社区

领取腾讯云代金券