什么是栈

栈也是一种线性表，但它是受到限制的线性表。

栈只允许在一端进行操作。

（1）栈中允许执行插入和删除操作的一端称为栈顶，不允许执行插入和删除操作的一端称为栈底；

.

（2）向一个栈中插入新元素又称为入栈、压栈。入栈之后该元素被放在栈顶元素的上面，成为新的栈顶元素；

.

（3）从一个栈中删除元素又称为出栈、弹栈，是把栈顶元素删除，使其相邻元素成为新的栈顶元素。

注意：

若要从栈中获取元素，只能通过栈顶指针取到栈顶元素，无法取得其它元素。

栈的相关操作

可对栈进行的基本操作如下:

• Create() (Init())︰创建栈（初始化栈);
• lsEmpty():判断栈是否为空;
• Push():进栈;
• Pop():出栈;
• getTop():获取栈顶元素。只读取栈顶元素，并不将元素弹出栈;
• getSize():获取栈的长度;
• Destory():销毁栈;

栈的实现

栈的顺序存储实现

栈的顺序存储也称为顺序栈，它利用一组 地址连续 的存储单元，依次存放 自栈底到栈顶 的元素，同时附设栈顶标识top来指示栈顶元素在顺序栈中的位置;

操作步骤：

顺序栈插入元素

顺序栈删除元素

栈的链式存储实现

栈的链式存储也称为链栈，它和链表的存储原理一样，都可以利用闲散空间来存储元素，用指针来建立各结点之间的逻辑关系。链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。它和链表的区别是，只能在一端进行各种操作。

操作步骤：

栈的应用

用栈实现四则运算

1、中缀转后缀

• 对于数字：直接输出；
  
• 对于符号：
  左括号：进栈，不管栈中是否有元素。
  运算符：若此时栈为空，直接进栈。
  若栈中有元素，则与栈顶符号进行优先级比较：
  若新符号优先级高，则新符号进栈（默认左括号优先级最低，直接入栈）。
  若新符号优先级低，将栈顶符号弹出并输出，之后使新符号进栈。
  右括号：不断将栈顶符号弹出并输出，直到匹配到左括号，再接着读取下一个符号；须注意，左右括号匹配完成即可，并不将其输出。
  
• 遍历结束：将栈中所有的符号弹出并输出。
  

2、后缀表达式的运算

• 对于数字：进栈；
• 对于符号：
  从栈中弹出右操作数；
  从栈中弹出左操作数；
  然后根据符号进行运算，将运算结果压入栈中。
• 遍历结束：将栈中所有的符号弹出并输出。

栈的递归应用

所谓递归就是程序调用自身的过程，它可以把一个大型的、复杂的问题层层转化为一个与原问题相似的、规模较小的问题来求解，递归策略只需少量的代码就可描述出解题过程中所需要的多次重复计算，大大地减少了程序的代码量。

一般来说，递归需要有临界条件：递归前进和递归返回段。否则递归将无限调用，永远无法结束程序，最后会造成内存崩溃。

递归调用过程

----3.4