简介

栈应该是一种非常简单并且十分有用的数据结构了。栈的特点就是先进后出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

本文已收录于 http://www.flydean.com/10-algorithm-stack/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」,懂技术，更懂你！