21 / 02 / 20

Java 数据结构丨栈

基本概念

数据结构从大的方向上分，可以分为逻辑结构和物理结构。逻辑结构是抽象的概念，它依赖于物理结构而存在。

物理结构可划分为：顺序存储结构与链式存储结构。

顺序存储结构：把数据元素存放在地址连续存储单元里，其数据间的逻辑关系和物理关系是一致的。例如数组。
链式存储结构：其中逻辑关系和物理关系没有多大的关系，因为其中的数据元素会产生变化。链式存储结构是把数据元素存放在任意的存储单元里，存储单元可以是连续的也可以是不连续的。当然也比顺序存储结构更加灵活。例如链表。

逻辑结构可划分为：线性结构与非线性结构。

线性结构：顾名思义，一条线性的结构，元素间的关系就是一对一的。例如线性表、栈、队列。
非线性结构：包括树形结构、图形结构等。例如树、图。

栈，stack，又称堆栈，是一种线性结构。与数组相比，访问它的元素是受限制的：栈只能在同一端(栈顶)进行操作，且只允许访问一个数据项，即最后插入的数据项。栈中的元素只能先入后出(First In Last Out，简称 FILO)，最先进入的元素存放的位置叫栈底，最后进入的元素存放的位置叫栈顶。

生活中也不缺可以体现出栈的特点的设计/例子。

例如：老师批改一叠作业，正常情况下都是先拿起最上面的一本，处理完这本之后，再去批改下一本，从上到下，直到被压在最后的一本，但是最后一本是最开始放的。

例如：兵乓球圆筒的一端封闭，另一端开口。往圆筒放入兵乓球，先放入的在圆筒底部，后放入的靠近圆筒入口。在圆筒直径条件限制下，只能按放入顺序相反的顺序取球。

实现栈

栈既可以用数组来实现，也可以用链表来实现。注意，如果用数组来实现，需要先规定栈的大小；如果用链表来实现，则不需要先规定栈的容量。

数组实现

class ArrayStack {
    // 最大长度
    private int maxSize;
    // 栈顶索引
    private int top;
    // 用于存储元素的数组
    private int[] stackArray;

    public ArrayStack(int val){
        maxSize = val;
        stackArray = new int[maxSize];
        top = -1;
    }
    // 栈空
    public boolean isEmpty(){
        return (top == -1);
    }
    // 栈满
    public boolean isFull(){
        return (top == maxSize - 1);
    }
    // 入栈
    public void push(int x){
        if (isFull()){
            throw new RuntimeException("栈已满！");
        }
        stackArray[++top] = x;
    }
    // 出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈是空的！");
        }
        return stackArray[top--];
    }
    // 查看栈顶
    public int peek(){
        return stackArray[top];
    }
    // 长度
    public int size(){
        return top + 1;
    }
    // 遍历输出：输出顺序与输入顺序相反
    public void show(){
        if (isEmpty()){
            System.out.println("栈是空的！");
        }else {
            int temp = top;
            while (temp != -1) {
                System.out.println(stackArray[temp]);
                System.out.print(" ");
                temp--;
            }
        }
    }
}

链表实现

class LinkStack<T>{
    // 栈顶
    private Node top;
    // 长度
    private int size = 0;
    // 节点
    private class Node{
        // 数据
        private T data;
        // next指针
        private Node next;
        public Node(T data){
            this.data = data;
        }
    }
    // 创建
    public LinkStack(){
        top = new Node(null);
    }
    // 栈空，链表没有定义存储限制，所以没有栈满
    public boolean isEmpty(){
        if (top.next == null){
            return true;
        }
        return false;
    }
    // 入栈
    public void push(T data){
        if (isEmpty()){
            top.next = new Node(data);
        }else{
            Node newNode = new Node(data);
            newNode.next = top.next;
            top.next = newNode;
        }
        size++;
    }
    // 出栈
    public T pop(){
        if (isEmpty()){
            System.out.println("栈是空的！");
            return null;
        }else {
            T val = top.next.data;
            top.next = top.next.next;
            size--;
            return val;
        }
    }
    // 获取栈顶元素
    public T peek(){
        if (isEmpty()){
            return null;
        }else{
            return top.next.data;
        }
    }
    // 栈的长度
    public int size(){
        return size;
    }
    // 输出
    public void show(){
        Node temp = top;
        if (isEmpty()){
            System.out.println("栈是空的！");
        }else{
            while(temp.next != null){
                temp = temp.next;
                System.out.print(temp.data + " ");
            }
        }
    }
}

常用 API

入栈(push)，就是把一个新元素放入栈中，只允许从栈顶一侧放入，下一个新元素放入的位置将成为新的栈顶。
出栈(pop)，就是把一个元素从栈中弹出，只有栈顶的元素才允许弹出，出栈元素的前一个元素将成为新的栈顶。
peek()，查看栈顶部的对象，但不对栈做任何改动。
size()，返回栈内元素的大小。
isEmpty()，测试栈是否为空，返回布尔值。
isFull()，测试栈是否为满，返回布尔值。

优劣

栈是一个重要的数据结构，其特性简而言之就是“先进后出”，可以用它辅助遍历二叉树的节点，也可以用它辅助查找图的顶点。在计算机中，大部分微处理器运用基于栈的体系结构。在 Windows 等大部分操作系统中，每个运行中的二进制程序都配有一个调用栈(Call Stack)和执行栈(Execution Stack)。当调用一个方法时，把它的返回地址和参数压入栈，方法结束返回时，那些数据就出栈，栈操作就嵌入在微处理器中。

用栈实现单词逆序；
中缀表达式求值；
实现十进制数和其他n进制数的转换;
用于解析某种类型的文本串，实现分隔符匹配；
......

栈操作所耗时间不依赖于栈中数据项的个数，因为入栈、出栈都是只影响到最后一个元素，不涉及比较和移动操作，所以无论是数组实现还是链表实现的，数据项入栈、出栈的时间复杂度都是常数级O(1)。

参考

Data Structure

Java