资讯专栏INFORMATION COLUMN

简单谈谈栈

王伟廷 / 3333人阅读

摘要:一前言计算机程序离不开算法和数据结构,数据结构这门学科就是为了让计算机能够以更加高效,简单,便捷的方式来存储和使用数据而产生的。返回一个布尔值,表示当前是否为空栈。

一、前言

计算机程序离不开算法和数据结构,数据结构这门学科就是为了让计算机能够以更加高效,简单,便捷的方式来存储和使用数据而产生的。本文简单介绍栈(Stack)和队列(Queue)的实现

二、图解

三、线性表

1、 顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素
2、 链式存储结构:用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,空间与内存没有线性关系

四、栈

1、只允许在一端进行插入和删除操作的线性表

2、 实现的功能

push:在最顶层加入数据。

pop:返回并移除最顶层的数据。

peek:返回最顶层数据的值,但不移除它。

empty:返回一个布尔值,表示当前stack是否为空栈。

2-1、初始化

private int[] arr;
    //常量用大写
    private final static int SIZE = 1;
    //栈的当前指针
    private int index;

    //构造器没有参数的
    public StackDemo() {
        arr = new int[SIZE];
        index = -1;
    }

2-2、push

//入栈
private void push(int target){
    if (index == SIZE){
        throw  new  StackOverflowError();
    }else {
        //刚开始为-1,要前加
        arr[++index] = target;
    }
}

2-3、peek

//返回栈顶元素
private int peek(){
    if (index == -1){
        throw new StackOverflowError();
    }else {
        return arr[index];
    }
}

2-4、empty

    //判空
    private boolean empty(){
        if (index == -1){
            return true;
        }
        return false;
    }

3、代码实现

import java.util.Arrays;

/**
 *
 * @author buer
 * @date 2019/1/20
 */
public class StackDemo {
    private int[] arr;
    //常量用大写
    private final static int SIZE = 1;
    //栈的当前指针
    private int index;

    //构造器没有参数的
    public StackDemo() {
        arr = new int[SIZE];
        index = -1;
    }

    //入栈
    private void push(int target){
        if (index == SIZE){
            throw  new  StackOverflowError();
        }else {
            //刚开始为-1,要前加
            arr[++index] = target;
        }
    }

    //出栈
    private int pop(){
        if (index == -1){
            throw new StackOverflowError();
        }else {
            return arr[index--];
        }
    }

    //返回栈顶元素
    private int peek(){
        if (index == -1){
            throw new StackOverflowError();
        }else {
            return arr[index];
        }
    }

    //判空
    private boolean empty(){
        if (index == -1){
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        StackDemo stackDemo = new StackDemo();
        stackDemo.push(1);
        System.out.println(stackDemo.toString());
        stackDemo.pop();
        System.out.println(stackDemo.toString());

    }

    @Override
    public String toString() {
        return "StackDemo{" +
                "arr=" + Arrays.toString(arr) +
                ", index=" + index +
                "}";
    }
}
应用

1、括号匹配

2、中缀表达式(人类的思考)和后缀表达式(计算机的计算)

3、递归

4、浏览器的前进后退功能

参考资料

https://zh.wikipedia.org
https://www.zhihu.com/question/21318658
http://www.ruanyifeng.com/blog/2013/11/stack.html

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/73089.html

相关文章

  • 谈谈javascript语法里一些难点问题(二)

    摘要:讲作用域链首先要从作用域讲起,下面是百度百科里对作用域的定义作用域在许多程序设计语言中非常重要。原文出处谈谈语法里一些难点问题二 3) 作用域链相关的问题 作用域链是javascript语言里非常红的概念,很多学习和使用javascript语言的程序员都知道作用域链是理解javascript里很重要的一些概念的关键,这些概念包括this指针,闭包等等,它非常红的另一个重要原因就...

    Enlightenment 评论0 收藏0
  • 谈谈JavaScript的词法环境和闭包(一)

    摘要:换句话说,定义在闭包中的函数可以记忆它被创建时候的环境。词法环境的概念定义摘自百科。一个词法环境由一个环境记录项和可能为空的外部词法环境引用构成。中使用词法环境管理静态作用域。 一个资深的同事在我出发去面试前告诫我,问JS知识点的时候千万别主动提闭包,它就是一个坑啊!坑啊!啊! 闭包确实是js的难点和重点,其实也没那么可怕,关键是机制的理解,可以和函数一起单独拿出来说说,其实关于闭包的...

    AlphaWatch 评论0 收藏0
  • 谈谈Java引用和Threadlocal的那些事

    摘要:容易导致内存泄漏。如果我们的强引用不存在的话,那么就会被回收,也就是会出现我们没被回收,被回收,导致永远存在,出现内存泄漏。缓存行和一次定位,不会有冲突由于使用数组,不会出现回收,没被回收的尴尬局面,所以避免了内存泄漏。 1 背景 某一天在某一个群里面的某个群友突然提出了一个问题:threadlocal的key是虚引用,那么在threadlocal.get()的时候,发生GC之后,ke...

    justjavac 评论0 收藏0
  • 谈谈javascript语法里一些难点问题(一)

    摘要:引子前不久我建立的技术群里一位问了一个这样的问题,她贴出的代码如下所示执行结果如下所示第一个第二个这是一个令人诧异的结果,为什么第一个弹出框显示的是,而不是呢这种疑惑的原理我描述如下一个页面里直接定义在标签下的变量是全局变量即属于对象的变量 1) 引子 前不久我建立的技术群里一位MM问了一个这样的问题,她贴出的代码如下所示: var a = 1; function hehe...

    huaixiaoz 评论0 收藏0

发表评论

0条评论

王伟廷

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<