栈，不就后进先出(手写一个栈)

什么是栈

大家好，我是bigsai，今天给大家聊聊栈这种数据结构。

栈在我们日常编码中遇到的非常多，很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException，栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化角斗场的狗洞)。

栈是这么定义的：

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

稍微介绍一下关键名词：

运算受限：也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端进行插入和删除。同样，队列也是运算受限，只能在两头操作。

线性表：栈也是一种线性表，前面详细介绍过线性表，它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现，他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。

栈顶栈底： 这个描述是偏向于逻辑上的内容，因为大家知道数组在末尾插入删除更容易，而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶，而链表可以头做栈顶。

栈的应用： 栈的应用广泛，比如你的程序执行查看调用堆栈、计算机四则加减运算、算法的非递归形式、括号匹配问题等等。所以栈也是必须掌握的一门数据结构。最简单大家都经历过，你拿一本书上下叠在一起，就是一个后进先出的过程，你可以把它看成一个栈。下面我们介绍数组实现的栈和链表实现的栈。

数组实现

数组实现的栈用的比较多，我们经常刷题也会用数组去实现一个简单的栈去解决简单的问题。

结构设计

对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data[]数组和一个top(int)表示栈顶位置。

那么初始化函数代码为：

private T data[];
private int top;
public seqStack() {
    data=(T[]) new Object[10];
    top=-1;
}
public seqStack(int maxsize)
{
    data=(T[]) new Object[maxsize];
    top=-1;
}

push插入

栈的核心操作之一push()：入栈操作。

• 如果top<数组长度-1。入栈,top++;a[top]=value;
• 如果top==数组长度-1；栈满。

pop弹出并返回首位

• 如果top>=0,栈不为空，可以弹出。return data[top--];
• 如下图，本来栈为1,2,3,4,5,6（栈顶）,执行pop操作,top变为3的位置并且返回4；

其他操作

例如peek操作时返回栈顶不弹出.所以只需满足要求时候return data[top]即可。

数组实现：

package 队栈;

public class seqStack<T> {

    private T data[];
    private int top;
    public seqStack() {
        data=(T[]) new Object[10];
        top=-1;
    }
    public seqStack(int maxsize)
    {
        data=(T[]) new Object[maxsize];
        top=-1;
    }
    boolean isEmpty()
    {
        return top==-1;
    }
    int length()
    {
        return top+1;
    }

    boolean push(T value) throws Exception//压入栈
    {
        if(top+1>data.length-1)
        {
            throw new Exception("栈已满");
        }
        else {
            data[++top]=value;
            return true;
        }
    }
    T peek() throws Exception//返回栈顶元素不移除
    {
        if(!isEmpty())
        {
            return data[top];
        }
        else {
            throw new Exception("栈为空");
        }
    }
    T pop() throws Exception
    {
        if(isEmpty())
        {
            throw new Exception("栈为空");
        }
        else {
           return data[top--];
        }
    }
    public String toString()
    {
        if(top==-1)
        {
            return "";
        }
        else {
            String va="";
            for(int i=top;i>=0;i--)
            {
                va+=data[i]+"  ";
            }
            return va;
        }
    }
}

链表实现

有数组实现，链表当然也能实现。对于栈的设计，大致可以分为两种思路：

• 像数组那样在尾部插入删除。大家都知道链表效率低在查询，而查询到尾部效率很低，就算用了尾指针，可以解决尾部插入效率，但是依然无法解决删除效率(删除需要找到前驱节点)，还需要双向链表。前面虽然详细介绍过双向链表，但是这样未免太复杂！
• 所以我们采用带头节点的单链表在头部插入删除，把头当成栈顶，插入直接在头节点后插入，删除也直接删除头节点后第一个节点即可，这样就可以完美的满足栈的需求。

结构设计

设计上和链表很相似，长话短说，短话不说，直接上代码就懂。
链表的节点：

static class node<T>
{
    T data;
    node next;
    public node() {    
    }
    public node(T value)
    {
        this.data=value;
    }
}

基本结构：

public class lisStack <T>{
    int length;
    node<T> head;//头节点
    public lisStack() {
        head=new node<>();
        length=0;
    }
    //其他方法
}

push插入

与单链表头插入一致，如果不太了解可以看看前面写的线性表有具体讲解过程。

和数组形成的栈有个区别，链式实现的栈理论上栈没有大小限制(不突破内存系统限制)，不需要考虑是否越界，而数组则需要考虑容量问题。

如果一个节点team入栈：

• 空链表入栈head.next=team;
• 非空入栈team.next=head.next;head.next=team;

pop弹出

与单链表头删除一致，如果不太了解请先看笔者队线性表介绍的。

和数组同样需要判断栈是否为空，如果节点team出栈：head指向team后驱节点。

其他操作

其他例如peek操作时返回栈顶不弹出.所以只需判空满足题意时候return head.next.data即可。而length你可以遍历链表返回长度，也可以动态设置(本文采取)跟随栈长变化。

链表实现：

package 队栈;

public class lisStack <T>{
    static class node<T>
    {
        T data;
        node next;
        public node() {    
        }
        public node(T value)
        {
            this.data=value;
        }
    }
    int length;
    node<T> head;//头节点
    public lisStack() {
        head=new node<>();
        length=0;
    }
    boolean isEmpty()
    {
        return head.next==null;
    }
    int length()
    {
        return length;
    }
    public void push(T value) {//近栈
       node<T> team=new node<T>(value);
       if(length==0)