脚踏实地海让路，持之以恒山能移

栈的知识学习

一、栈的基本概念 

二、栈的顺序存储及基本操作

       1.栈的顺序存储结构

       2.顺序栈的操作

                 初始化

                 入栈操作

                 出栈操作

                 取栈顶元素

                 判断栈是否为空

                 判断栈是否为满

三、栈的链式存储及基本操作

         1.栈的链式存储结构

          2.链栈的操作

                 初始化

                 入栈操作

                 出栈操作

                 取栈顶元素

                 判断栈是否为空

                 链栈的销毁

一、栈的基本概念 

栈是只能在一端进行插入和删除的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。当栈中没有元素时称为空栈。

栈主要有两个操作：插入和删除。栈的插入操作称为入栈（压栈），栈的删除操作称为出栈（弹栈）。栈的主要特点是”后进先出“，即出栈元素只能是位于栈顶的元素，而入栈元素也只能放在栈顶的位置。因此，栈是一种操作受限的线性表。

如图，栈中的元素按照a1、a2......an的顺序入栈，出栈顺序按照an......a2、a1的顺序出栈

二、栈的顺序存储及基本操作

1.栈的顺序存储结构

利用顺序存储方式实现的栈又称为顺序栈。由于栈顶位置会随着入栈和出栈而变化，因此可用一个整型变量来表示当前栈顶的位置，通常称该整型变量为栈顶指针。

顺序栈的类型定义如下：

 ps ：我把难懂的英文也注释出来了，这样便于读者朋友们的阅读和理解

栈空时，栈顶指针 top = -1；栈满时，栈顶指针 top = MAXSIZE -1。入栈前，栈顶指针加1；出栈后，栈顶指针减1。

2.顺序栈的操作

(1) 初始化

初始化栈就是要构造一个空栈，算法如下：

 (2)  入栈操作

在栈顶插入一个新元素 x,使 x 成为新的栈顶元素，同时栈顶指针发生变化。算法如下：

  (2)  出栈操作

将栈顶元素从栈中删除，同时栈顶指针发生变化。算法如下：

 (4)取栈顶元素

将栈顶元素作为结果返回，栈顶指针不变化。算法如下：

(5) 判断栈是否为空

算法如下：

 (6) 判断栈是否为满

算法如下：

 三、栈的链式存储及基本操作

 1.栈的链式存储结构

利用链式存储方式实现的栈又称为链栈。链栈中的结点采用Node结点类型。由于栈是操作受限的线性表，对栈中元素的插入和删除只能在栈顶进行，因此实现链栈的单链表不需要带头结点。

如图，栈顶指针top就是单链表的头指针。

 链栈的类型定义如下：

 可以用LinkStack定义指针，该指针就代表了一个链栈，如：LinkStack;

2.链栈的操作

(1)初始化

建立一个无头结点的单链表，算法如下：

 (2)入栈操作

在无头结点的单链表中进行表头插入，算法如下：

 (3)出栈操作

在单链表中进行表头结点的删除，算法如下：

 (4)取栈顶元素

返回栈顶指针所指向结点的数据域，算法如下：

 (5)判断栈是否为空

 (6)链栈的销毁

类似于单链表的销毁函数，需要释放链栈所占用的空间

小结

以上就是最近关于栈的知识学习总结，下期我会出栈的其他运用以及队列的相关知识。希望各位批评指正，我会努力改进完善!