数据结构05 栈

发表于 | 分类于
这篇文章要总结的是栈，主要从以下几个方面来进行总结。

笔记仓库：https://github.com/nnngu/LearningNotes

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

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("");
    }

}

测试结果：