3栈与队列教学讲义.ppt

第三章 栈和队列;【学习指南】 在这一章中，主要是学习如何在求解应用问题中 适当地应用栈和队列，栈和队列在两种存储结构中的 实现都不难，但应该对它们了如指掌，特别要注意它 们的基本操作实现时的一些特殊情况，如栈满和栈空 、队满和队空的条件以及它们的描述方法。 ;线性表和栈及队列的插入和删除操作对比如下： 　 　　 　　 　插 入 　　　　　删 除 　 线性表： Insert(L,i,x)　 　Delete(L,i) 　　 　 (1≤i≤n+1)　 　(1≤i≤n) 　　 栈： Insert(L,n+1,x) 　Delete(L,n) 　　　队列：Insert(L,n+1,x)　 Delete(L,1) ;3.1 栈 3.1.1 栈的类型定义; 通常称往栈顶插入元素的操作为“入栈”，称删除栈顶元素 的操作为“出栈”。因为后入栈的元素先于先入栈的元素出栈， 故被称为是一种“后进先出”的结构，因此又称LIFO表。;栈的抽象数据类型定义如下： ADT Stack { 　 数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 } 　 数据关系：R1＝{ ai-1 , ai | , ai-1,ai∈D, i=2,...,n } 　　 约定an端为栈顶，a1端为栈底。;基本操作： 　　InitStack(S) 　　　操作结果：构造一个空栈 S。 　　DestroyStack(S) 　　　初始条件：栈 S 已存在。 　　　操作结果：栈 S 被销毁。 　　ClearStack(S) 　　　初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。;3.1.2 栈的存储表示和操作的实现;栈顶指针和栈中元素之间的关系 ;void InitStack (SqStack S) {　// 构造一个空栈 S 　　S.base = (SelemType )malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE ; return OK; };void GetTop (SqStack S, SElemType e) { 　// 若栈不空，则用 e 返回S的栈顶元素，并返回 // OK；否则返回ERROR 　 if (S.top == S.base) return ERROR; 　　e = *( S.top-1); 　　// 返回非空栈中栈顶元素 　　return OK; 　};void Push (SqStack S, SElemType e) {　// 插入元素 e 为新的栈顶元素， if (S.top – S.base = S.stacksize) { // 栈已满，追加存储空间 S.base = (SElemType *)realloc (S.base , (S.stacksize + STACKINCREMENT ) * sizeof(Elemtype)); if(!S.base) exit( overflow); S.top = S.base + S.stacksize; 　　 S.stacksize ++= STACKINCREMENT; }　　　　　　　　　 *S.top++ = e ; // 插入新的元素 return OK; };void Pop (SqStack S, SElemType e) { 　// 若栈不空，则删除S的栈顶元素，用 e 返回其值， 　 // 并返回 OK；否则返回 ERROR 　 if (S.top == S.base) return ERROR; 　 e = *- - S.top; 　 // 返回非空栈中栈顶元素,栈顶指针前移 　 return OK; } ;链栈即为栈的链式存储结构。 ;结构定义： 　　typedef struct { 　　　LinkList top; // 栈顶指针 　　　int length; 　 // 栈中元素个数 　　} SqStack; ;vo