数据存储——栈（stack）

本章节的源代码位于gitee上，想要下载的请点击数据存储——栈

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

只要接触Java，就会接触到栈，因为在Java执行的时候，所有的方法都是存放在堆栈之中的，通过不断地出栈不断的执行。最先入栈的最后执行，最后入栈的最先执行。如果接触过递归调用，应该就知道，递归调用就是一个入栈和出栈的过程，如果递归调用没有一个确定值就会造成堆栈异常。

相关的堆栈执行原理就如下图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uQD4dBih-1602050010977)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201007090738379.png)]

接下来我们就来编写一个栈。栈的编写依然采用链表的方式。该类主要编写如下几个方法。

empty() //如果栈为空返回true，否则返回false
size() //返回栈中元素的个数
pop() //删除栈顶元素但不返回其值
top() //返回栈顶的元素，但不删除该元素
push() //在栈顶压入新元素

栈的创建与添加数据

栈依然使用链表来进行扩展，不过与之前的链表有所不同的在于，数据只能在栈顶输出。那么这个时候我们的结点就需要重新设计了，需要将指向下一个结点的变量变为指向上一个结点，我们通过这要给指针实现对整个栈的数据压栈和弹出栈的操作，大致的操作流程如下图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A2fpYcbo-1602050010990)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201007124302506.png)]

interface IStack<T>{
    void push(T data);//在栈顶压入新元素
}
class StackImpl<T> implements IStack<T>{
    private Node top;//栈顶
    private int size;//栈中数据
    @Override
    public void push(T data) {//添加数据
        Node node = new Node(data);
        if(this.top== null){//判断栈是否有数据
            this.top = node;
        } else {
            node.last = this.top;//压入数据
            this.top = node;
        }
        this.size ++;//栈中数据+1
    }
    private class Node<T>{//链表结点
        private T data;
        private Node next;
        private  Node(T data){
            this.data = data;
        }
    }
}

如果只看以上的代码就会发现和单项链表的添加部分是大同小异的，无非就是将结点中存储的地址改变而已，单项链表用于存储下一个结点，栈用于存储上一个结点的数据。

需要说明一点的是，栈的操作最好使用两个指针，一个指针始终指向栈底，一个指针始终指向栈顶。之后再判断数据是否全部弹出的时候通过比较两个指针的地址是否相同。但是我认为大家都那么操作，我这里想只用一个指针来操作。

栈数据操作（弹出元素、堆栈是否为空）

无论是使用双指针还是和我这样使用单指针，再操作数据的时候都是一样的，移动栈顶的指针即可。将压栈操作逆向操作即可。这里我们一次性将剩下的四种方法全部实现了。它们的原理都是一样的。

empty() //如果栈为空返回true，否则返回false
size() //返回栈中元素的个数
pop() //删除栈顶元素但不返回其值
top() //返回栈顶的元素，但不删除该元素

相关代码为：

@Override
public boolean empty() {
    return this.top!=null;//通过判断指针指向情况
    //return this.size != 0;//通过判断个数也是可以的
}
@Override
public int size() {
    return this.size;
}
@Override
public void pop() {
    this.top();
}
@Override
public T top() {
    Object data = this.top.data;
    this.top = top.last;//指针上移
    this.size --;
    return (T) data;
}

总结

堆栈的操作和链表的操作极为类似，会链表掌握堆栈很容易。需要注意的就是栈为先进后出的操作逻辑。

全部代码如下，也可以去gitee上下载

interface IStack<T>{
    void push(T data);//添加数据
    boolean empty();//如果栈为空返回true，否则返回false
    int size();//返回栈中元素的个数
    void pop();//删除栈顶元素但不返回其值
    T top();//返回栈顶的元素，但不删除该元素
}
class StackImpl<T> implements IStack<T>{
    private Node top;//栈顶
    private int size;//栈中数据
    @Override
    public void push(T data) {//添加数据
        Node node = new Node(data);
        if(this.top== null){//判断栈是否有数据
            this.top = node;
        } else {
            node.last = this.top;//压入数据
            this.top = node;
        }
        this.size ++;//栈中数据+1
    }
    @Override
    public boolean empty() {
        return this.top!=null;//通过判断指针指向情况
        //return this.size != 0;//通过判断个数也是可以的
    }
    @Override
    public int size() {
        return this.size;
    }
    @Override
    public void pop() {
        this.top();
    }
    @Override
    public T top() {
        Object data = this.top.data;
        this.top = top.last;//指针上移
        this.size --;
        return (T) data;
    }
    private class Node<T>{//链表结点
        private T data;
        private Node last;//保存上一个结点
        private  Node(T data){
            this.data = data;
        }
    }
}
public class SimulateStackDemo {
    public static void main(String[] args) {
        IStack<String> stack = new StackImpl<>();
        stack.push("A");
        System.out.println("弹出的数据为："+stack.top()+"堆栈中剩余："+stack.size());
        stack.push("B");
        stack.push("C");
        stack.push("D");
        while(stack.empty()){
            System.out.println("弹出的数据为："+stack.top()+"堆栈中剩余："+stack.size());
        }
    }
}

其他数据存储知识点

数据存储——单向链表

数据存储——双向链表

数据存储——实现ArrayList