例2、一个栈的输入序列为1,2,3,若在入栈的过程中允 许出栈,则可能得到的出栈序列是什么? 解:可以通过穷举所有可能性来求解: ①1入1出,2入2出,3入3出,即123; ②1入1出,2、3入,3、2出,即132; ③1、2入,2出,3入3出,即231; ④1、2入,2、1出,3入3出,即213; ⑤1、2、3入,3、2、1出, 卩321 合计有5种可能性
6 例2、一个栈的输入序列为1,2,3，若在入栈的过程中允 许出栈，则可能得到的出栈序列是什么？ 解：可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入3出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性
例3、一个栈的输入序列是12345,若在入栈的过 程中允许出栈,则栈的输出序列43512可能实现 吗?12345的输出呢? 解 43512不可能实现,主要是其中的12顺序不 能实现; 12345的输出可以实现,每压入一数便立即 弹出即可
7 例3、一个栈的输入序列是12345，若在入栈的过 程中允许出栈，则栈的输出序列43512可能实现 吗？12345的输出呢？ 解： 43512不可能实现，主要是其中的12顺序不 能实现； 12345的输出可以实现，每压入一数便立即 弹出即可
堆栈抽象数据类型 数据集合:{a,a1,…,an1}a1的数据类型为 DataType 操作集合:(1) StackInitiate(s)初始化堆栈S (2) StackNotEmpty(S)堆栈S非空否 (3) StackPush(S,x)入栈 (4)StackPop(s, d) 出栈 (5)StackTop(s, d) 取栈顶数据元素 等
8 二、堆栈抽象数据类型 数据集合：{ a0 , a1 , … , an-1 ｝ ai的数据类型为 DataType 操作集合：(1)StackInitiate(S) 初始化堆栈S (2)StackNotEmpty(S) 堆栈S非空否 (3)StackPush(S,x) 入栈 (4)StackPop(S,d) 出栈 (5)StackTop(S,d) 取栈顶数据元素 等
、堆栈的顺序表示和实现 1、顺序(堆)栈 顺序存储结构的堆栈。 2、顺序栈的存储结构 它是利用一组地址连续的存储 单元依次存放自栈底到栈顶的数据元 顺序栈S栈顶top 素,同时设指针top指示栈顶元素的 a an-1 当前位置。用C语言定义为 typedef struct ai t DataType stack MaxStackSize; int top, a1 Seastack: a0栈底base
9 三、堆栈的顺序表示和实现 1、顺序（堆）栈 顺序存储结构的堆栈。 2、顺序栈的存储结构 它是利用一组地址连续的存储 单元依次存放自栈底到栈顶的数据元 素，同时设指针top指示栈顶元素的 当前位置。用C语言定义为： typedef struct { DataType stack[MaxStackSize]; int top; }SeqStack; a0 a1 …… an-1 顺序栈S ai …… an 栈底base 栈顶top
问:顺序表和顺序栈的操作有何区别? 以线性表S=(a0,a1,…,an2,an1)为例 栈顶top 顺序表S 顺序栈S 高地址□ 表尾 高地址 an an-1 Si ai ai a1 a1 低地址 栈底ba se ao 表头 低地址 ao 写入:S[il=a 压入(PUSH:S[top++]=an 读出:e=S[i 弹出(POP):e=S[-top 前提:一定要预设栈顶指针top
10 a0 a1 …… an-1 顺序栈S ai …… 问：顺序表和顺序栈的操作有何区别？ 表头 表尾 低地址 高地址 写入：S[i]= ai 读出： e= S[i] 压入(PUSH): S[top++]=an 弹出( POP) : e=S[--top] 低地址 高地址 S[i] a0 a1 ai an-1 …… 顺序表S …… an 以线性表 S= (a0 , a1 , …. , an-2 , an-1)为例 栈底base 栈顶top 前提：一定要预设栈顶指针top 栈顶top