栈的定义引入

情景引入

        在浏览器网页上大家都很熟悉的两个按键，前进和后退： 

        或者是Word里的撤销按键：

        像这样的按键，大家都知道功能是回退一个网页或者操作，就像倒放一样一步一步的回退，类似这样的操作，就是栈的思想。

栈的定义

        栈，是限定仅在表尾进行插入和删除操作的线性表。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

栈的基本操作

• 初始化InitStack(&S);
• 判空Empty(S)；判断一个栈是否为空，若栈为空则返回true，否则返回false。
• 进栈Push(&S, x)；进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
• 出栈Pop(&S, &x)；出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
• 读栈顶元素GetTop(S);
• 遍历栈PrintStack(&S);
• 销毁栈DestroyStack(&S)；栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

进出栈的形式 

        栈的先入后出如果单纯这么来说，可能会让大家陷入某种误区，我们来看：

 我们有一个栈，a，b，c三个元素，如果a先进栈，那么a一定是最后一个出栈吗？

情况一

a先进栈，b之后进栈，c最后进栈。

 c先出栈，b之后出栈，a最后出栈

 情况二

a先进栈

 然后a出栈

 b进栈，c进栈

。。。 

 

栈的作用 

        栈的引入简化了程序设计的问题，划分为不同关注层次，使得思考范围缩小更能聚焦于我们要解决的问题核心。其中所有的数据存入或取出，只能在浮动的一端称栈顶进行，严格按照“先进后出”的原则存取，位于其中间的元素，必须在其栈上部后进栈者诸元素逐个移出后才能取出。