[数据结构与算法]数据结构解析-栈

栈（stack）又名堆栈，他是一种运算受限的线性表。限定仅在表尾进行插入和删除的线性表。这一端被称为栈顶，相对的，把另外一端称之为栈底。向一个栈中插入新元素又称之为进栈，入栈或者压栈，他是将新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除一个栈顶元素称之为出栈或者退栈，说白了就是将栈顶元素删除，使其相邻的元素成为新的栈顶元素

栈的基本概念

????栈的本质含义就是指数据暂时存储的地方，所以才有进栈，出栈的说法。所以系统或者数据结构栈中数据内容的读取和插入不能混为一谈，压入是增加数据，弹出是删除数据，这些操作只能是从栈顶即是最低地址作为约束接口界面的入手操作，但是读取栈中的数据是随便的，没有接口约束之说

????栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。他是按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读取出来），栈具有记忆作用，对栈的插入和删除操作中，不需要改变栈底指针。插入一般称之为进栈（PUSH），删除称之为退栈（POP），栈也称为先进后出表。

????栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用所需要的维护信息，这常常称之为堆栈帧或者活动记录，一般包含以下几方面信息：
1、函数的返回地址和参数
2、临时变量：包含函数的非静态局部变量以及编译器自动生成的其他临时变量

$栈模型$

算法实例

根据上述给出的栈模型，不难得出以下算法模型

1、进栈（PUSH）

• ①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
• ②置TOP=TOP+1（栈指针加1，指向进栈地址）；
• ③S(TOP)=X，结束（X为新进栈的元素）；

2、退栈（POP）

• ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
• ②X=S(TOP)，（退栈后的元素赋给X）：
• ③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

模拟栈结构（java）

方法

package dataStructure;

/**
 * Created by jdx on 2022/3/3 下午3:40
 * 模拟栈：使用一位数组模拟栈的数据结构，假设栈的默认容量为 6
 * 实现功能：
 * 1、可以存储 Java 中任意类型的数据
 * 2、提供 push 方法模拟压栈（栈满了，要有提示信息）
 * 3、提供 pop 方法模拟弹栈（栈空了，要有提示信息）
 * 4、设置栈帧，指向栈顶元素
 * 5、编写测试程序
 */
public class stack {
    //定义数组
    private Object[] element;
    //定义指针
    private int index;

    /*get set 方法*/

    public Object[] getElement() {
        return element;
    }

    public void setElement(Object[] element) {
        this.element = element;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    /*无参数构造*/
    public stack() {
        this.element = new Object[6];
        this.index = -1;
    }


    public stack(Object[] element, int index) {
        this.element = element;
    }

    /*压栈方法*/
    public void push(Object object) {
        if (this.index >= element.length - 1) {
            System.out.println("栈已经满了，压栈失败！！！！");
            return;
        }
        this.element[++index] = object;
        System.out.println("压入" + object + "元素成功" + "  下标为：" + index);
    }

    /*出栈方法*/
    public void pop() {
        if (this.index <= -1) {
            System.out.println("栈已空，弹栈失败！！！！");
            return;
        }
        System.out.println("弹出" + element[index] + "成功");
        this.element[index--] = null;
        System.out.println("指针指向：" + index);
    }
}

测试类

package basics;

import dataStructure.stack;

/**
 * Created by jdx on 2022/3/3 下午3:50
 */
public class stackTest {
    public static void main(String[] args) {
        stack sta = new stack();
        //压栈
        sta.push(new Object());
        sta.push(new Object());
        sta.push(new Object());
        sta.push(new Object());
        sta.push(new Object());
        sta.push(new Object());
        sta.push(new Object());
        System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
        //出栈
        sta.pop();
        sta.pop();
        sta.pop();
        sta.pop();
        sta.pop();
        sta.pop();
        sta.pop();
    }
}

运行结果：

压入java.lang.Object@35fb3008元素成功  下标为：0
压入java.lang.Object@7225790e元素成功  下标为：1
压入java.lang.Object@54a097cc元素成功  下标为：2
压入java.lang.Object@36f6e879元素成功  下标为：3
压入java.lang.Object@5a61f5df元素成功  下标为：4
压入java.lang.Object@3551a94元素成功  下标为：5
栈已经满了，压栈失败！！！！
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
弹出java.lang.Object@3551a94成功
指针指向：4
弹出java.lang.Object@5a61f5df成功
指针指向：3
弹出java.lang.Object@36f6e879成功
指针指向：2
弹出java.lang.Object@54a097cc成功
指针指向：1
弹出java.lang.Object@7225790e成功
指针指向：0
弹出java.lang.Object@35fb3008成功
指针指向：-1
栈已空，弹栈失败！！！！