图示栈的三种常用基本操作 GetTop(s, &e) 初始条件:栈S已存在且非空。 操作结果:用e返回S的栈顶元素。 a1a2…an Push(&s, e) 初始条件:栈S已存在。 操作结果:插入元素e为新的栈顶元素 a1a……ane Pop(as, &e) 初始条件:栈S已存在且非空。 操作结果:删除S的栈顶元素,并用e返回其值。 a1 a a1/a
a1 a2 … … an GetTop(S, &e) 初始条件：栈S 已存在且非空。 操作结果：用e 返回 S 的栈顶元素。 e Push(&S, e) 初始条件：栈S 已存在。 操作结果：插入元素e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈S 已存在且非空。 操作结果：删除S 的栈顶元素，并用e 返回其值。 图示栈的三种常用基本操作 a1 a2 … … an a1 a2 … … an-1 an-1 an
啁。鵠的表录你实现 1、顺桃 3、链桃
4.1.2 栈的表示和操作实现 1、顺序栈 2、链 栈
1、能的喜录与窦现一顺序情 顺序栈的存储结构实现:—维数组sM] 栈满 栈空) p top stop F15 top top E 4 op 432 to to p 5432 to top DCBA top top- top 找空 进栈 出栈 设数组维数为M 钱顶top指向实际栈顶tp-空,此时出栈,则下溢( underfl) 后的空位置,初值为0p=M栈满,此时入栈,则上溢( overflow)
顺序栈的存储结构实现：一维数组s[M] top=0 1 2 3 4 5 0 栈空 栈顶指针top,指向实际栈顶 后的空位置，初值为0 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F top top top top top 1 2 3 4 5 A 0 B C D E top F top top top top top 栈空 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) 1、栈的表示与实现──顺序栈
l的喜录与实现一顺桃 顺序栈基本操作的实现: 栈顶的初始化:S.top= S base 栈空: S base==Stop 栈满:Stop- S. base>=S. .stacksize -入栈:*S.top++=e,出栈:e=*-S,op op b top top ba base ase base→ 空栈 a进栈 b进栈 约定:top指向栈顶元寨的下一个位置
1、栈的表示与实现──顺序栈 顺序栈基本操作的实现： – 栈顶的初始化：S.top = S.base – 栈空：S.base == S.top – 栈满：S.top - S.base >= S.stacksize – 入栈：*S.top ++ = e，出栈：e = *--S.top base 空栈 a 进栈 b 进栈 a top base top base top a b 约定：top指向栈顶元素的下一个位置
表和栈的操作区别一一对线性表s=(a,a2,ant,an) 顺序表V[n] 表尾 顺序栈S 高地址 t 高地址 an+ a an a ai a a2 低地址 表头 a 低地址 栈底base a1 写入:v=a EE入:PUsH(an) 出:X= 弹出:PoP(x 前提:一定要预设栈顶指针top!
a1 a2 …… an 顺序栈S ai …… 表和栈的操作区别—— 对线性表 s = ( a1, a2, …., an-1, an ) 表头 表尾 栈底base 栈顶top 低地址 高地址 写入：v[i]= ai 读出：x= v[i] 压入：PUSH (an+1) 弹出：POP (x) 前提：一定要预设栈顶指针top！ 低地址 高地址 v[i] a1 a2 ai an …… 顺序表V[n] …… an+1