1、栈的概念

栈(stack)又称堆栈,是限制在表的一端进行插入和删除的 线性表 。其限制是仅允许在表的一端进行插入和删除的操作，不允许在其他位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端成为栈顶( top ),栈顶保存的元素成为栈元素。相对的，表的另一端称为栈底(Bottom)。当栈中没有数据元素时称为空栈，向一个栈插入元素又称为进栈或者入栈；从一个栈中删除元素称为出栈或者退栈。

在上图中，当ABCD 入栈之后，出栈时序列为DCBA，即“后进先出”。在解决实际问题时，如果碰到了数据的使用具有“后进先出”的特性，就预示着可以使用堆栈来存储和使用这些数据，堆栈的基本操作除了进栈、出栈操作外，还有判空、取栈顶元素等操作。如果把上述存储过程比作一个瓶子的话，这个瓶子是有“底”的。

2、顺序栈

由于栈是运算受限的线性表，除了操作不同外，线性表的存储结构对栈也是适用的。利用顺序存储方式实现的栈称为顺序栈。

2.1入栈操作思想

根据顺序栈的存储特点，要将某一元素压入栈内，则要进行如下操作:

(1)先判断栈是否已经装满元素，未装满才能进行入栈操作，否则不操作。

(2)栈顶指针先自增，给需要进栈的元素腾出内存空间。

(3)再将要入栈的元素放入腾出的内存空间里，就是把入栈的元素赋值给对应的数组元素。

【例】某班已有2名同学张三、李四的学生信息存放在栈内，现有(学号10003，王五) 新同学加入，请将其信息压入栈中。 压入对应结点的过程如下:

栈顶指针先自增，给需要进栈的元素腾出内存空间，再往空间里压入元素( 学号10003,王五)，如上图所示。

2.2入栈操作流程图：

顺序栈的学生元素存放在data数组中，length为栈的总长度，top为栈顶指针，则学生元素入栈 程序流程图 如下图所示:

学生元素入栈流程图

2.3出栈操作思想

根据顺序栈的存储特点，要取出栈内某一元素，则要进行如下操作:

(1) 先判断栈是否有元素，如果有元素时才能进行出栈操作，否则不操作。

(2 )再将要出栈的元素取出放在内存空间里。

(3 )栈顶指针自减。

【例】某班已有3名同学张三、李四、王五的学生信息存放在栈内，现需要从栈中取出一位同学的信息进行审查，并显示取出该同学的信息。

取出对应结点的过程如下:

出栈前如图1所示，先把需要出栈的元素(10003，王五)取出放在内存空间里，再把栈顶指针自减如图2所示。

2.4出栈操作流程图

顺序栈的学生元素存放在data数组中，length为栈的总长度，top为栈顶指针，则学生元素出栈流程图如3.7所示

3、链栈

用链式存储结构实现的栈称为链栈。其结点结构与 单链表 的结构相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域element,另一个是存放指向下一个结点的对象引用(即指针)next。

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点，所以链式堆栈通常不带头结点。

通常将链栈表示成下图的形式。

链栈的基本操作也是进栈和出栈操作。

3.1进栈操作思想

根据链栈的存储特点，要将某一个新节点s压入栈内，则要进行如下操作：

(1) 处理新结点s的后继，这个后继就是原本的栈顶结点。

(2) 将栈顶指针top 重新指向新结点s即可。

【例】某班已有两名同学张三、李四的学生信息存放在链栈内，现有(10003，王五) 新同学来加入，请将其信息压入链栈中。

将对应结点压人链栈内的过程如下:

入栈前如图3.1所示。

生成新节点（10003，王五），处理新节点的后继，使其后继指向原本的栈顶节点，如图3.2所示。

将栈顶指针top重新指向新节点（10003，王五）即可，如果3.3所示。

3.2进栈操作流程图

链栈中插入的学生元素存放在node中，top为栈顶指针，curlen为栈的长度，则学生元素入栈程序流程图如图3.4所示。

3.3出栈操作思想

根据链栈的存储特点，要弹出某一个结点，则要进行如下操作:

(1) 在栈顶指针top 非空的情况下，保存弹出结点。

(2) 将栈顶指针top 下移一个元素，即top= top.next。

【例】 某班已有3 名同学张三、李四、王五的学生信息存放在链栈内，现需要从链栈中取出一位同学的信息进行审查，并显示取出的信息。

接下来弹出对应结点的过程如图3.5所示。

3.4出栈操作流程图

链栈中弹出学生元素存放在ni中，top为栈顶指针，curlen为栈的长度，则学生元素出栈程序流程图如3.6所示。

链栈出栈流程图

关注小编，一起进步！！！

最后祝大家新的一年天天开心，心想事成！