堆栈的结构

堆栈，简称栈，栈是一种受限制的线性表，它只允许在线性表的一端进行插入和删除操作，俗称入栈和出栈。我们把允许插入和删除的一端叫做栈顶，另外一端叫做栈底，当线性表中没有任何元素的时候叫做空栈。由于只能在线性表的一端进行入栈和出栈操作，所以就导致了堆栈有一个最基本的规律先进后出，先入栈的元素后出去，后入栈的元素先出去。
所以堆栈的算法逻辑和数组链表的逻辑类似，只是操作受到了一些限制。

栈的实现

堆栈可以用数组来实现，也可以用链表来实现。我们称这两种实现为顺序栈和链栈。对于数组和链表的内容这里就不在做过多的介绍了，前面的课程已经给大家做过数组和链表相关的内容。本章节中我们先用数组实现顺序栈。下一章节再实现链栈。

栈的定义

我们再程序中声明一个Stack类，用于表示顺序栈，类中包含了入栈、出栈、是否空栈、是否满栈等算法，具体定义如下：

internal class Stack
{
    int[] dataArr;//存放堆栈的数组
    int top = -1;//栈顶指针
    int size;//栈容量 其实就是dataArr的长度
}

Stack类中我们顶一个一个数组dataArr来存放栈元素，我们默认数组下标0为栈底，依次从栈底开始入栈。top表示栈顶的数组下标。top始终指向栈顶元素，当栈为空的时候，top=-1。同时还定义了一个字段size表示栈的容量，也就是这个栈最多可以存放多少个元素，其实就是dataArr的长度。
所以大家可以把顺序栈的操作看成对数组尾部元素的一系列操作就会简单很多，说的再简单一点，顺序栈的操作就是对数组的操作。因为前面大家已经学过一维数组的相关操作，所以栈的操作会简单很多。

算法1：入栈

入栈需要先判断栈是否满了，如果满了就需要对栈进行扩容。我们这里采取扩容策略是将dataArr的长度直接增加一倍。如果栈不满，则执行赋值操作dataArr[top]=value，同时栈顶指针向后移动一位top++，具体示例代码如下：

public void Push(int data)
{
    //栈满 扩容
    if (top == (size - 1))
    {
        int[] newData = new int[size * 2];
        for (int i = 0; i < size; i++)
        {
            newData[i] = this.dataArr[i];
        }
        this.dataArr = newData;
        size = size * 2;
    }
    //赋值 栈顶指针后移
    dataArr[++top] = data;
}

算法2：出栈

先判断一下栈是否为空(top==-1时为空栈)，如果为空，直接抛出异常。如果不为空，返回return dataArr[top--]。该操作返回栈顶元素，同时将栈顶指针前移一位，具体示例代码如下：

public int Pop()
{
    if (top == -1)
    {
        throw new Exception("栈空了!");
    }
    return dataArr[top--];
}

算法3：获取栈顶元素

先判断一下栈是否为空(top==-1时为空栈)，如果为空，直接抛出异常。如果不为空，直接返回栈顶元素 return dataArr[top];，注意该操作只是查看一下栈顶元素的值，并不会移动栈顶指针top，而出栈会移动栈顶指针top。具体示例代码如下：

public int Peek()
{
    if (top == -1)
    {
        throw new Exception("空栈！");
    }
    return dataArr[top];
}

算法4：栈是否为空

当栈顶指针top==-1的时候，栈为空，具体示例代码如下：

public bool IsEmpty()
{
    return top == -1;
}

算法5：栈是否已满

当栈顶指针top指向数组dataArr最后一个索引位置的时候，栈就满了，具体示例代码如下：

public bool IsFull()
{
    return top == (size - 1);
}

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/05Stack.cs

总结

顺序栈其实就是借助一个数组实现堆栈的顺序存储，所以对顺序栈的操作实际上就是对数组的操作。

顺序栈