关于算法:看动画学算法之栈stack

1次阅读

共计 2151 个字符，预计需要花费 6 分钟才能阅读完成。

栈应该是一种非常简单并且十分有用的数据结构了。栈的特点就是先进后出 FILO 或者后进先出 LIFO。

实际上很多虚拟机的构造都是栈。因为栈在实现函数调用中十分的无效。

明天咱们一起来看学习一下栈的构造和用法。

栈一种有序的线性表，只能在一端进行插入或者删除操作。这一端就叫做 top 端。

定义一个栈，咱们须要实现两种性能，一种是 push 也就是入栈，一种是 pop 也就是出栈。

当然咱们也能够定义一些其余的辅助性能，比方 top：获取栈上最顶层的节点。isEmpty: 判断栈是否为空。isFull: 判断栈是否满了之类。

先看下入栈的动画：

再看下出栈的动画：

具备这样性能的栈是怎么实现呢？

一般来说栈能够用数组实现，也能够用链表来实现。

如果应用数组来实现栈的话，咱们能够应用数组的最初一个节点作为栈的 head。这样在 push 和 pop 栈的操作的时候，只须要批改数组中的最初一个节点即可。

咱们还须要一个 topIndex 来保留最初一个节点的地位。

实现代码如下：

public class ArrayStack {

    // 理论存储数据的数组
    private int[] array;
    //stack 的容量
    private int capacity;
    //stack 头部指针的地位
    private int topIndex;

    public ArrayStack(int capacity){
        this.capacity= capacity;
        array = new int[capacity];
        // 默认状况下 topIndex 是 -1，示意 stack 是空
        topIndex=-1;
    }

    /**
     * stack 是否为空
     * @return
     */
    public boolean isEmpty(){return topIndex == -1;}

    /**
     * stack 是否满了
     * @return
     */
    public boolean isFull(){return topIndex == array.length -1 ;}

    public void push(int data){if(isFull()){System.out.println("Stack 曾经满了，禁止插入");
        }else{array[++topIndex]=data;
        }
    }

    public int pop(){if(isEmpty()){System.out.println("Stack 是空的");
            return -1;
        }else{return array[topIndex--];
        }
    }
}

下面的例子中，咱们的数组大小是固定的。也就是说 stack 是有容量限度的。

如果咱们想构建一个有限容量的栈应该怎么做呢？

很简略，在 push 的时候，如果栈满了，咱们将底层的数组进行扩容就能够了。

实现代码如下：

public void push(int data){if(isFull()){System.out.println("Stack 曾经满了，stack 扩容");
            expandStack();}
        array[++topIndex]=data;
    }

    // 扩容 stack，这里咱们简略的应用倍增形式
    private void expandStack(){int[] expandedArray = new int[capacity* 2];
        System.arraycopy(array,0, expandedArray,0, capacity);
        capacity= capacity*2;
        array= expandedArray;
    }

当然，扩容数组有很多种形式，这里咱们抉择的是倍增形式。

除了应用数组，咱们还能够应用链表来创立栈。

应用链表的时候，咱们只须要对链表的 head 节点进行操作即可。插入和删除都是解决的 head 节点。

public class LinkedListStack {

    private Node headNode;

    class Node {
        int data;
        Node next;
        //Node 的构造函数
        Node(int d) {data = d;}
    }

    public void push(int data){if(headNode == null){headNode= new Node(data);
        }else{Node newNode= new Node(data);
            newNode.next= headNode;
            headNode= newNode;
        }
    }

    public int top(){if(headNode ==null){return -1;}else{return headNode.data;}
    }

    public int pop(){if(headNode ==null){System.out.println("Stack 是空的");
            return -1;
        }else{
            int data= headNode.data;
            headNode= headNode.next;
            return data;
        }
    }

    public boolean isEmpty(){return headNode==null;}
}

本文的代码地址：

learn-algorithm