ACCESS公共基础-栈及列队.pdf

特殊线性表——栈 特殊线性表——栈 特殊线性表——栈 特殊线性表——栈 n 栈的逻辑结构 n 栈的逻辑结构 栈的示意图 入栈 出栈 栈的示意图 n 栈：限定仅在表尾进行插入和删除操作的线 n 栈：限定仅在表尾进行插入和删除操作的线 性表。 性表。 n 空栈：不含任何数据元素的栈。 n 空栈：不含任何数据元素的栈。 栈顶 插入：入栈、进栈、压栈 n 允许插入和删除的一端称为栈顶，另一端称 c 插入：入栈、进栈、压栈 n 允许插入和删除的一端称为栈顶，另一端称 为栈底。 栈顶 删除：出栈、弹栈 为栈底。 b 删除：出栈、弹栈 栈顶 （a , a , ……, a ） 栈底 a 1 2 n 栈底 栈顶 特殊线性表——栈 特殊线性表——栈 栈的逻辑结构 栈的逻辑结构 栈的示意图 入栈 栈的示意图 例：有三个元素按a、b、c的次序依次进栈，且每个 出栈 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 元素只允许进一次栈，则可能的出栈序列有多少种？ Ø情况1： 栈顶 c 插入：入栈、进栈、压栈 栈顶 b （PUSH ） 栈顶 c 栈顶 删除：出栈、弹栈 b 栈底 a 栈顶 （POP ） 栈底 a 栈的操作特性：后进先出 栈的操作特性：后进先出 栈的逻辑结构 栈的逻辑结构 栈的逻辑结构 栈的逻辑结构 例：有三个元素按a、b、c的次序依次进栈，且每个 例：有三个元素按a、b、c的次序依次进栈，且每个 例：有三个元素按a、b、c的次序依次进栈，且每个 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 元素只允许进一次栈，则可能的出栈序列有多少种？ 元素只允许进一次栈，则可能的出栈序列有多少种？ 元素只允许进一次栈，则可能的出栈序列有多少种？ Ø情况1： Ø情况2 ： 出栈序列：c