数据结构05 栈

这篇文章要总结的是栈,主要从以下几个方面来进行总结。

1、栈是什么 2、栈的存储结构 3、栈的常见操作及代码实现

1、栈是什么

栈是一种特殊的线性表,它限定了只能在表的一端进行插入与删除操作。因此,栈就是后进先出 Last In First Out (LIFO) 的线性表。

线性表分为顺序表和链表,所以栈分为顺序栈链式栈,为了方便演示,下文所使用的栈都是顺序栈。 

它的应用场景有很多,比如手枪弹夹里面的子弹,只能从一端塞入或者取出子弹。

2、栈的存储结构

顺序栈的代码实现:

SeqStack.java

/**
 * 自己封装一个顺序栈
 */
public class SeqStack {
    // 使用数组来存放元素
    public Object[] data;
    
    // 栈顶指针
    public int top;
    
    public SeqStack(int length) {
        data = new Object[length];
    }
}

3、栈的常见操作及代码实现

3-1、初始化

实现思路:用指定大小的 length 实例化一个 SeqStack,然后使top指针指向-1

代码:

SeqStackOperate.java

public class SeqStackOperate {
    /**
     * 初始化
     * @param length
     * @return
     */
    public SeqStack init(int length) {
        SeqStack seqStack = new SeqStack(length);
        seqStack.top = -1;
        return seqStack;
    }
}

3-2、进栈

实现思路:将top指针加1,然后将新元素插入到top指针指向的位置。

代码:

SeqStackOperate.java 中添加方法

    /**
     * 进栈
     * @param seqStack
     * @param data
     */
    public void push(SeqStack seqStack, Object data) {
        // 检查栈是否满了
        if (seqStack.top == seqStack.data.length - 1) {
            return;
        }
        seqStack.top++;
        seqStack.data[seqStack.top] = data;
    }

3-3、出栈

实现思路:删除top指针指向的元素,并使top指针减1

代码:

SeqStackOperate.java 中添加方法

    /**
     * 出栈
     * @param seqStack
     * @return
     */
    public Object pop(SeqStack seqStack) {
        // 检查栈是否为空
        if (seqStack.top == -1) {
            return null;
        }
        Object obj = seqStack.data[seqStack.top];
        seqStack.data[seqStack.top] = null;
        seqStack.top--;
        return obj;
    }

3-4、获取栈顶元素

实现思路:与出栈相似,但是不删除栈顶元素。

代码:

SeqStackOperate.java 中添加方法

    /**
     * 获取栈顶元素
     *
     * @param seqStack
     * @return
     */
    public Object getTopData(SeqStack seqStack) {
        // 检查栈是否为空
        if (seqStack.top == -1) {
            return null;
        }
        return seqStack.data[seqStack.top];
    }

3-5、判断是否栈空

实现思路:判断top指针是否等于-1就可以

代码:

SeqStackOperate.java 中添加方法

    /**
     * 判断是否栈空
     * @param seqStack
     * @return
     */
    public boolean isEmpty(SeqStack seqStack) {
        return seqStack.top == -1;
    }

3-6、判断是否栈满

实现思路:检查top指针的值与数组长度减1是否相等,如果相等则为栈满。

代码:

SeqStackOperate.java 中添加方法

    /**
     * 判断是否栈满
     * @param seqStack
     * @return
     */
    public boolean isFull(SeqStack seqStack) {
        return seqStack.top == seqStack.data.length - 1;
    }

3-7、获取栈中元素个数

实现思路:top指针的值加1就是栈中的元素个数。

代码:

SeqStackOperate.java 中添加方法

    /**
     * 获取栈中元素个数
     *
     * @param seqStack
     * @return
     */
    public int getLength(SeqStack seqStack) {
        return seqStack.top + 1;
    }

4、测试

添加一个用来测试的类:StackTest.java

public class StackTest {

    public static void main(String[] args) {
        SeqStackOperate seqStackOperate = new SeqStackOperate();

        // 初始化一个栈,最大长度为5
        SeqStack seqStack = seqStackOperate.init(5);

        // 看看能否放进6个元素
        seqStackOperate.push(seqStack, 1);
        seqStackOperate.push(seqStack, 2);
        seqStackOperate.push(seqStack, 3);
        seqStackOperate.push(seqStack, 4);
        seqStackOperate.push(seqStack, 5);
        seqStackOperate.push(seqStack, 6);

        // 输出栈当前的长度
         int length = seqStackOperate.getLength(seqStack);
        System.out.println("栈当前的长度:" + length);
        System.out.println("");

        // 出栈
        Object obj = seqStackOperate.pop(seqStack);
        System.out.println("出栈的元素是 ---- " + obj);
        System.out.println("");

        // 输出栈当前的长度
        length = seqStackOperate.getLength(seqStack);
        System.out.println("栈当前的长度:" + length);
        System.out.println("");

        // 输出当前的栈顶元素
        obj = seqStackOperate.getTopData(seqStack);
        System.out.println("当前的栈顶元素是 ---- " + obj);
        System.out.println("");
    }

}

测试结果:

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

面试题53(考察求职者对String声明变量在jvm中的存储方法)

(单选题) 1、有如下一段代码,请选择其运行结果() public class StringDemo{ private static final Stri...

2963
来自专栏java初学

值传递和引用传递

2536
来自专栏个人随笔

房上的猫:StringBuffer类

一.使用StringBuffer类  StringBuffer类位于java.lang包中,是String类的增强类  步骤:   1.声明StringBuff...

35215
来自专栏IT可乐

JDK1.8源码(六)——java.util.LinkedList 类

  上一篇博客我们介绍了List集合的一种典型实现 ArrayList,我们知道 ArrayList 是由数组构成的,本篇博客我们介绍 List 集合的另一种典...

3485
来自专栏程序员互动联盟

【java概念】String的常用方法

1、length() 字符串的长度   例:char chars[]={'a','b'.'c'};     String s=new String(chars)...

3618
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题21包含min函数的栈

题目:实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。    分析:要获取栈的最小值,我们首先想到的思路就是使用一个全局...

3708
来自专栏禁心尽力

Java Collection开发技巧

Java Collection(集合) ? 集合中的一些技巧: 通过Collections类的静态方法,可以对集合进行一些操作 1 java....

24410
来自专栏无题

链式存储线性表(LinkedList)数据结构解析

LinkedList内部是通过链表来实现的 一、节点分析 LinkedList内部是通过链表来实现的,那么就少不了节点,所以在源码中必然能找到这样一个节点。 ...

3326
来自专栏郭耀华‘s Blog

Java集合框架(四)—— Queue、LinkedList、PriorityQueue

Queue接口   Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存...

3816
来自专栏维C果糖

详述 Java 语言中的 String、StringBuffer 和 StringBuilder 的使用方法及区别

1 简介 在 Java 语言中,共有 8 个基本的数据类型,分别为:byte、short、int、long、float、double、boolean和char,...

2105

扫码关注云+社区

领取腾讯云代金券