数据结构-3.1.栈

这是一篇关于数据结构-3.1.栈思维导图，只允许在一端插入删除的线性表，先进后出FILO。

栈Stack

• 定义：只允许在一端插入删除的线性表，先进后出FILO
• 性质：n个元素进栈，出栈元素不同排列的个数为（卡特兰数）
• 存储结构
  • 顺序栈
    • 基本操作
      • 创：S.top=-1
      • 销：由于定义了一个静态数组，故函数调用结束时系统自动回收
      • 增：S.data[++S.top]=x 先移指针后入栈
      • 删：x=S.data[S.top--]
      • 查(读栈顶元素)：x=S.data[S.top]
      • 如何判空/判满？：S.top==-1/S.top==MaxSize-1
  • 链栈
    • 用链式方式存储的栈
    • 实现方式
      • 带头结点
      • 不带头结点（推荐）
    • 出入栈都是在链表的表头进行
    • 优点：不存在栈满上溢的情况，且便于多个栈共享空间
  • 共享栈
    • S.top0==-1；S.data[++S.top]=x 从栈底往栈顶入栈
    • S.top1=MaxSize；x=S.data[--S.top] 从栈顶往栈底入栈
    • 判满：top0+1==top1