数据结构PPT课件--第3章-栈和队列.pptxVIP

1第三章 栈和队列 2什么是栈？什么是队列？栈和队列都是线性表但是其操作是受限的ana2a1栈顶栈底出栈进栈a1an-1an出队列进队列队首队尾 3本章内容3.1 栈3.2 栈的实现3.3 栈的应用3.4 队列3.5 离散事件模拟 43.1 栈栈：限定仅能在表尾一端进行插入、删除操作的线性表；栈的特点：后进先出（LIFO）ana2a1栈顶top栈底base出栈进栈 5栈的应用-函数调用 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：将所有的实参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。 6栈的应用-函数调用从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。 7栈的应用-函数调用多个函数嵌套调用的规则是：后调用先返回 ！此时的内存管理实行“栈式管理”void main( ){ void a( ){ void b( ){ … … … a( ); b( ); … …}//main }// a }// bMain的数据区函数a的数据区函数b的数据区 8 ADT Stack { 数据对象： 数据关系： 基本操作：…… } ADT Stack3.1 栈的类型定义D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底 9栈的基本操作结构性操作InitStack(S)操作结果：构造一个空栈S。DestroyStack(S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。ana2a1栈顶top栈底base 10栈的基本操作StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。ana2a1栈顶top栈底base 11栈的基本操作ClearStack(S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。GetTop(S, e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。ana2a1栈顶top栈底base 12栈的基本操作Pop(S, e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。ana2a1栈顶栈底出栈an-1a2a1an-1栈底栈顶e= an 13栈的基本操作Push(S, e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。ana2a1栈顶栈底栈顶ana2a1栈底e进栈e 143.2 栈类型的实现1）顺序栈－类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { SElemType * top; //栈顶 SElemType * base; //栈底 int stacksize; //栈的大小 } SqStack;ana2a1basetop 15顺序栈的操作可扩充栈的操作进栈和上溢栈顶指针top，指向实际栈顶后的下一个位置，初值为 top=basetop进栈A栈当前空间不足，需扩充BCDE设栈的初始分配量为 Stacksize = STACK_INIT_SIZE。 若 top == Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充 STACK_INCREMENT； 若无可利用的存储空间，则上溢 (overflow)。toptoptoptop栈空base top1234012340topbasestacksize SqStack s;s 顺序栈的操作出栈和下溢1612340ABCDE出栈toptoptoptoptoptoptop==base栈空若top==base, 栈空，此时出栈，则下溢(underflow)base 171）顺序栈的实现InitStack