栈

特点：由于只能在栈顶进行插入和删除操作，使得后进栈的元素先出栈，先进栈的元素后出栈 因此栈是一种后进先出(Last In First Out，LIFO)的数据结构 。

栈

• 定义:只允许在一端进行插入、删除操作的线性表
• 说明：
  • 首先：栈是一种线性表 栈元素具有线性关系， 受限体现在:只能在一端进行插入、删除 栈顶(top):允许插入、删除的一端 栈底(bottom):不允许插入、删除的一端(栈底是固定的，最先进栈的只能在栈底) 空栈:不含任何元素的栈 栈顶指针:用于指示栈顶位置 栈顶指针:用于指示栈顶位置(顺序栈的栈顶指针:指示栈顶下标的整型变量 链式栈的栈顶指针:记录栈顶元素所在结点地址的指针) 栈的插入:一般称之为入栈、压栈 栈的删除:一般称之为出栈、弹栈
• 特点：由于只能在栈顶进行插入和删除操作，使得后进栈的元素先出栈，先进栈的元素后出栈 因此栈是一种后进先出(Last In First Out，LIFO)的数据结构
• 基本操作： ①InitStack(S):初始化操作，建立一个空栈 S。 ② StackEmpty(S):判空栈操作，若S为空栈，返回一个真值。 ③Push(S，x):进栈操作，在S栈顶插入一个元素x。 ④Pop(S,*y):出栈操作，若栈S不空，删除栈顶元素并保存在*y中。 ⑤GetTop(S,*y):取栈顶元素操作，若栈S不空，则取栈顶元素保存在*y中。
• 栈的顺序存储结构
  • 定义
    • 简称顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素 （top类似于顺序表中的length，设置一个top指针指示当前栈顶的位置，MaxSize是最大长度，length是实际长度）
  • 说明：
    • 栈空： top==O时
    • 栈满： top==MAXSIZE时
    • 进栈： 先进一个元素·指针top加1
    • 出栈 ：先指针top减1·出一个元素
    • 栈顶指针top： 始终指向栈顶元索的下一个位置
    • 上溢 ：栈满时如还有元素要进栈，它可能使有用信息丢失，因此要尽量避免
    • 下溢： 栈空时还要出栈，下溢常常用来作为控制转移的条件或算法结束的标志
• 栈的链式存储结构
  • 定义：
    • 栈也可以采用单链表表示，简称为链栈。（在链栈中，应将链表的尾结点定为栈底，首元结点定为栈顶)