第三章栈和队列 栈 令队列 令递归
❖ 栈 ❖ 队列 ❖ 递归 第三章栈和队列
栏( Stack 定义:是限定仅在表尾进行插入或删除操 作的线性表。 允许插入和删除的一端出栈进栈 称为栈顶op),另一端 称为栈底 ( bottom) op 特点:后进先出IFO) bottom- 1
栈 ( Stack ) ▪ 定义:是限定仅在表尾进行插入或删除操 作的线性表。 ▪ 允许插入和删除的一端 称为栈顶(top)，另一端 称为栈底(bottom) ▪ 特点：后进先出 (LIFO) a1 top bottom an . . . . 出栈 进栈
栈的主要操作 ADT Stack /对象由数据类型为 StackData的元素构成 int push( stack“S, StackData x);〃进栈 int Pop( stack *s, StackData&x);/出栈 int GetTop( stack“S, StackData&x);/取栈顶 void Initstack(stack "S); 置空栈 int StackEmpty( stack*S);判栈空否 int StackFull(stack *S); /判栈满否
栈的主要操作 ADT Stack { //对象由数据类型为StackData的元素构成 int Push (stack *S, StackData x); //进栈 int Pop (stack *S, StackData &x); //出栈 int GetTop (stack *S, StackData &x); //取栈顶 void InitStack (stack *S); //置空栈 int StackEmpty (stack *S); //判栈空否 int StackFull (stack *S); //判栈满否 }
栈的表示和实现 顺序栈:栈的顺序存儲结构,利用一组地址连 续的存储单元依次存放自栈底到栈顶的数据元素, 指针top指向栈顶元素在顺序栈中的下一个位置, base为栈底指针,指向栈底的位置。 top top op base base→a base-人d 空栈 a进栈 b进栈
栈的表示和实现 ▪ 顺序栈：栈的顺序存储结构，利用一组地址连 续的存储单元依次存放自栈底到栈顶的数据元素， 指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 base 空栈 a 进栈 b 进栈 a a b top base top base top
top top elcba p d b base b base edcb base→a e进栈 ∫进栈溢出 e出栈
top top a b c d e e 进栈 a b c d e f 进栈溢出 a b d e 出栈 c base base base top