Java数据结构与算法[原创]——栈

hiyang 发布于2019-08-19 10:42 / 627人阅读

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。方法调用编写的程序在进行方法函数调用时，会完成对方法的压栈操作，等方法执行结束后，对应的会完成对方法的弹栈操作。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的栈的概念、存储结构、栈的特点以及栈的适用场景，另外会穿插介绍面试中的一些经典问题供读者参考。

1.栈的相关概念

栈是一种有着特殊操作规则的数据结构——后进先出（LIFO，Last In First Out），这也是栈的最重要的一个特点。栈又叫做堆栈（Stack），这里说明一下不要讲堆栈和堆（Heap）的概念混淆，事实上栈和堆是两个不同的概念，后面的文章会介绍堆。一般来讲，栈有两个操作：一个是进栈（Push），也叫压栈或入栈，另一个是出栈（Pop）或叫弹栈、退栈。

2.栈的存储结构

栈一般使用一段连续的空间进行存储，通常预先分配一个长度可以简单的使用数组来实现，具体存储结构如图：

通过上图可以看到只有一个方向可以对栈内元素进行操作，栈中最下面的元素位置叫栈底，通常定义为数组的第0个元素，最上面的元素叫栈顶。一般而言，定义一个栈需要声明栈的促使容量，当放入的栈中的元素大于栈的容量时，就需要考虑扩容，否则溢出。

3.java代码实现

以下是栈的java代码，此处以整型元素为例。

import java.util.Arrays;

public class Stack {
    private int size = 0;  //栈顶位置
    private int[] array;
    
    public Stack(){
        this(10);
    }
    public Stack(int init) {   
        if(init <= 0){
            init = 10;
        }
        array = new int[init];
    }
    
    /**
     * 入栈操作
     * @param item 入栈的元素
     */
    public void push(int item){
        if(size == array.length){
            array = Arrays.copyOf(array, size*2);   //扩容操作
        }
        array[size++] = item;
    }
    
    /**
     * 获取栈顶元素，但栈顶元素不出栈
     * @return 栈顶元素
     */
    public int peek(){
        if(size == 0){  //空栈
            throw new IndexOutOfBoundsException("栈是空的");
        }
        return array[size-1];
    }
    
    /**
     * 出栈，同时获取栈顶元素
     * @return
     */
    public int pop(){
        int item = peek();  //获取栈顶元素
        size--;  //直接使元素个数减1，不用清除元素，下次入栈会覆盖旧元素的值
        return item;
    }
    
    /**
     * 判断栈是否已满
     * @return
     */
    public boolean isFull(){
        return size == array.length;
    }
    
    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    
    public int getSize(){
        return size;
    }    
}

测试程序：

public class StackTest {
    public static void main(String[] args) {
        Stack s = new Stack(3);  //设置栈的初始容量为3
        s.push(2);
        s.push(5);
        s.push(7);
        s.push(10);    //此时扩容，自底向顶 2—>5->7->10
        System.out.println("栈顶位置是："+s.getTop()); //栈顶指针为4，数组长度为3*2=6        
        System.out.println("获取栈顶元素："+s.peek());  //获取但不弹栈
        System.out.println("弹出栈顶元素："+s.pop());//弹栈返回10,自底向顶 2—>5->7
        System.out.println("弹出栈顶元素："+s.pop());//弹栈返回7,自底向顶 2—>5
        s.push(66);   //入栈后，自底向顶 2—>5->66
        System.out.println("弹出栈顶元素："+s.pop());//弹栈返回66
        System.out.println("弹出栈顶元素："+s.pop());//弹栈返回5
        System.out.println("弹出栈顶元素："+s.pop());//弹栈返回2
        System.out.println("弹出栈顶元素："+s.pop());//抛出异常，提示为空栈
    }
}

4.栈的特点

栈的特点显而易见，只能从一段进行元素的压入和弹出，先进去的后出来。

5.栈的应用场景

根据栈先入后出的特点，以下场景的问题适合用栈来解决：

1）逆序输出
将所有元素依次压入栈中，然后依次弹出即可

2）编译器的语法检查
在大多数编程语言中，一般括号都是成对出现，遇到括号的左半部分，则进行入栈（push）操作，遇到括号右半部分则立即与栈顶（top）元素匹配，匹配成功则弹栈（pop），否则报错。

3）数制转换（10进制转换任意进制）
数制转换通常采用取余倒置，此处不再展开。

4）方法调用
编写的程序在进行方法（函数）调用时，CPU会完成对方法的压栈操作，等方法执行结束后，对应的CPU会完成对方法的弹栈操作。当然除此之外，cpu产生中断后，首先进行压栈操作，将打断的程序运行数据一一入栈，中断服务程序执行完后把入栈的运行数据按照相反的顺序依次出栈，恢复中断前的运行状态，CPU 开始返回中断前的地方继续运行。

GPU云服务器云服务器机器算法与java 算法与数据结构数据结构与算法数据结构与算法教程

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

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

Java数据结构与算法[原创]——队列

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。队列和栈类似，也是一个遵循特殊规则约束的数据结构。将没有元素的队列称之为空队，往队列中插入元素的过程称之为入队，从队列中移除元素的过程称之为出队。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的队列（queue）的概念、存储结构、队列的特点...

韩冰 2019-08-19 10:43 评论0 收藏0
面试问我 Java 逃逸分析，瞬间被秒杀了。。

摘要：记得几年前有一次栈长去面试，问到了这么一个问题中的对象都是在堆中分配吗说明为什么当时我被问得一脸蒙逼，瞬间被秒杀得体无完肤，当时我压根就不知道他在考什么知识点，难道对象不是在堆中分配吗最后就没然后了，回去等通知了。。记得几年前有一次栈长去面试，问到了这么一个问题: Java中的对象都是在堆中分配吗？说明为什么！当时我被问得一脸蒙逼，瞬间被秒杀得体无完肤，当时我压根就不知道他在考什么...

CastlePeaK 2019-08-19 11:43 评论0 收藏0
刚写完排序算法，就被开除了…

摘要：刚写完这段代码，就被开除了栈长前些天刚写完上面这篇文章，没几天，又来一个悲剧。。。说到这个程序员，让我想起了最近审查代码时候的几个坑，真是让人哭笑不得。。。示例直接不行写这么绕，还把逻辑写错了。刚写完这段代码，就被开除了…… 栈长前些天刚写完上面这篇文章，没几天，又来一个悲剧。。。据说是一个月薪 9K 的 Java 程序员，因老板让他写一个排序算法，然后他就写了一段屌炸天的休眠排序...

klivitamJ 2019-08-16 13:41 评论0 收藏0
java篇 - 收藏集 - 掘金

摘要：进阶多线程开发关键技术后端掘金原创文章，转载请务必将下面这段话置于文章开头处保留超链接。关于中间件入门教程后端掘金前言中间件 Java 开发人员最常犯的 10 个错误 - 后端 - 掘金一、把数组转成ArrayList 为了将数组转换为ArrayList，开发者经常... Java 9 中的 9 个新特性 - 后端 - 掘金Java 8 发布三年多之后，即将快到2017年7月下一个版...

OpenDigg 2019-08-15 10:42 评论0 收藏0
长知识 - 收藏集 - 掘金

摘要：问题是这些服务都是第三方提供的，不能保证它们的响应时间，快的话美团点评分布式生成系统后端掘金背景在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。 SpringBatch 读取 txt 文件并写入数据库 - 后端 - 掘金SpringBatch 读取 txt 文件并写入数据库... Java 进阶-多线程开发关键技术 - 后端 - 掘金原创文章，转载请务必将下面这段话置于文章...

SimpleTriangle 2019-08-15 10:52 评论0 收藏0