【数据结构】【线性表】栈的基本概念(附c语言源码)

栈的基本概念

讲基本概念还是回到数据结构的三要素：逻辑结构，物理结构和数据运算。

• 从逻辑结构来讲，栈的各个数据元素之间是通过是一对一的线性连接，因此栈也是属于线性表的一种
• 从物理结构来说，栈可以是顺序存储和顺序表一样，也可以是链式存储和链表一样，但栈的主要特点不是存储的位置关系，而是操作限制：栈的插入或删除都只可以在其一端进行。
• 从数据运算来讲，栈的插入和删除都只能在一端进行，因此其基本操作没有删除和插入一说，而是讲进栈和出栈；除了这两个基本操作外，栈还包括初始化栈，销毁栈，读栈顶元素等操作。
  栈的基本术语
  我们可以将栈视为一个长形的桶，把数据元素看成一个个小球，然后一个个将球放进桶里的过程。
• 栈底元素：最先放进去的小球在桶的最下面，我们叫它栈底元素；
• 栈顶元素：最后放进去的小球在桶的最上面，我们叫它栈顶元素；
• 栈顶：所以我们把能插入和删除的那一端称为栈顶，栈顶是可变的
• 栈底：不能插入和删除的呢一段称为栈底，栈底是固定的
• 空栈：栈里面没有一个元素称为空栈
  
  数据元素进栈顺序：1->2->3
  数据元素出栈顺序：3->2->1
  栈的特点是先进后出(LIFO)
  栈的基本操作
• 创建栈：构建一个空栈S，分配内存空间
• 销毁栈：释放栈内元素及其内存空间
• 进栈：在栈未满时，将元素x从栈顶压入栈称为新栈顶
• 出栈：在栈不是空栈时，弹出栈顶元素，下一个元素称为新栈顶元素
• 查栈顶元素
• 判别栈是否为空栈
  栈操作的常见错误
• 栈下溢(underflow) top=0 即为空栈 empty 时执行出栈
• 栈上溢(overflow) top>n n为栈的长度