栈思维导图
栈介绍
树图思维导图提供 栈 在线思维导图免费制作，点击“编辑”按钮，可对 栈 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：48b91bd314cd5a795630d9e25dc1947c
思维导图大纲
栈（stack）思维导图模板大纲
定义
只准在一端进行插入删除操作的线性表，允许插入的一端叫栈顶，另一端叫栈底；也叫后进先出表
特性：后进先出（LIFO）
术语：栈顶（top），栈底（bottom），空栈
值得注意
n个不同元素进栈，出栈元素不同排列个数如上，称为卡特兰数
作用：逆序；栈是实现过程和函数等子程序的必须结构
输入序列：指可能的输入序列，是无序的
合法序列：满足输入序列的有序序列
顺序栈
顺序存储，用静态数组实现，并记录栈顶指针
实现时插入操作top++，因此，栈是限定仅在表尾插入删除的线性表！
基本操作
创建，增、删、查，时间复杂度都是O(1)
两种实现方法
初始化时top=-1，top指向栈顶元素，同时也是判栈空条件
入栈
s[++top] = x
出栈
x = s[top--]
获取栈顶
x = s[top]
栈满
top = maxsize - 1
初始化时top = 0，top指向下一个插入位置，同时也是判空条件
入栈，出栈
上一个的++，--换位置
获取栈顶
x = s[top-1]
栈满
top = maxsize
共享栈
两个站共享同一片内存空间，两个栈从两边向中间增长，即两栈的栈底分别设在内存空间的两端
初始化
top0 = -1，top1 = maxsize
栈满
top0 + 1 == top1；也称两栈顶指针相邻 or 两栈顶指针值的差的绝对值为1
链栈
带头结点
头插即入栈，头后删即出栈
此时首元节点才是栈顶，但是栈顶指针指向头结点
不带头结点
入栈
s->next = top;top = s;
出栈
top = top->next
对比顺序栈与链栈
顺序栈
优点：存取速度快，插入删除方便
缺点：栈满会发生溢出，如果分配空间太大会有资源浪费
链栈
优点：便于插入删除，不存在栈满问题
缺点：需要额外存储空间存放每个结点的链接指针
程序中使用多个栈
分别建立多个独立的栈
算法出错率小，栈的使用安全
各个栈不能共享存储空间
多个栈共享一个存储空间
充分利用存储空间
移动频繁，时间开销大
多个独立链栈
没有溢出问题，通过指针各自独立操作，操作安全
每个链表结点要附加一个指针，存储利用率低
多个栈共存，最好选择这种存储结构
基本操作
创建、销毁
增（入栈）、删（出栈），只能在栈顶操作
查，获得栈顶元素但不删除
判空
沪公网安备 31011502019485号
上海工商