第三章栈和队列
第三章 栈和队列
第一节栈 311栈的类型定义 栈( Stack)是限定只能在表的一端进行插入和 删除操作的线性表。 在表中,允许插入和删除的一端称作“栈顶 (top)”, 不允许插入和删除的另一端称作"栈底 (bottom) 入栈 出栈 栈元素 栈顶元素
第一节 栈 3.1.1 栈的类型定义 • 栈（Stack）是限定只能在表的一端进行插入和 删除操作的线性表。 • 在表中，允许插入和删除的一端称作“栈顶 (top)”， • 不允许插入和删除的另一端称作"栈底 (bottom)"
栈必须按“后进先出”的规则进行操作 栈只允许在表尾一端进行插入和删除 ·通常称往栈顶插入元素的操作为“入栈” 称删除栈顶元素的操作为“出栈”。 因为后入栈的元素先于先入栈的元素出栈, 故被称为是一种后进先出"的结构,因此 又称LFo( Last in first out)表
• 栈必须按“后进先出”的规则进行操作 • 栈只允许在表尾一端进行插入和删除 • 通常称往栈顶插入元素的操作为“入栈” • 称删除栈顶元素的操作为“出栈”。 • 因为后入栈的元素先于先入栈的元素出栈， 故被称为是一种"后进先出"的结构，因此 又称LIFO（Last In First Out）表
类型定义 ADT Stack i 数据对象:D={aa1∈ Elem Set,i=12,,n,n20} 数据关系:R1={<aa1斗a1a1∈D,=2,,n} 约定a端为栈顶,a1端为栈底。 基本操作: Initstack(&s) 操作结果:构造一个空栈S。 Destroy Stack&s 初始条件:栈S已存在。 操作结果:栈S被销毁
类型定义 • ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ | ai-1 , ai ∈D, i=2,...,n } 约定an端为栈顶， a1端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁
ClearStack(&s) 初始条件:栈S已存在。 操作结果:将S清为空栈。 StackEmpty(s) 初始条件:栈S已存在。 操作结果:若栈S为空栈,则返回TRUE, 否则返回 FALSE。 StackLength(s) 初始条件:栈S已存在。 操作结果:返回栈S中元素个数,即栈 的长度。 GetTop(s, &e) 初始条件:栈S已存在且非空 操作结果:用e返回S的栈顶元素
• ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 • StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE， 否则返回FALSE。 • StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回栈 S 中元素个数，即栈 的长度。 • GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素
°Push(&s,e) 初始条件:栈S已存在 操作结果:插入元素e为新的栈顶元素。 °Pop(&s,&e) 初始条件:栈S已存在且非空。 操作结果:删除S的栈顶元素,并用e 返回其值。 StackTraverse(S, visit()) 初始条件:栈S已存在且非空,vsit() 为元素的访问函数。 操作结果:从栈底到栈顶依次对S的每个 元素调用函数visi(),一旦 visit()失败,则操作 失败。 3 ADT Stack
• Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 • Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 • StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( ) 为元素的访问函数。 操作结果：从栈底到栈顶依次对S的每个 元素调用函数visit( )，一旦visit( )失败，则操作 失败。 • } ADT Stack
3.1.2栈的存储表示和操作的实现 顺序栈类型的定义 ·结构定义: typedef struct E| emType*base;∥/存储空间基址 int top ∥栈顶指针 int stac ksize;∥允许的最大存储空 间以元素为单位 3 Stack Sto S tackie
3.1.2 栈的存储表示和操作的实现 • 顺序栈类型的定义 • 结构定义： typedef struct { ElemType *base; // 存储空间基址 int top; // 栈顶指针 int stacksize; // 允许的最大存储空 间以元素为单位 } Stack;
void InitStack (Stack &S, int maxsize) ∥构造一个最大存储容量为 maxsize的空栈 if (maxsize = 0 maxsize= MAXLISTS忆zE s base= new SElemType[maxsize]; if(! s base)ext(1);存储分配失败 s. stacksize maxsize: stop=0;∥空栈中元素个数为0
• void InitStack (Stack &S，int maxsize) { // 构造一个最大存储容量为 maxsize 的空栈 S if (maxsize == 0) maxsize = MAXLISTSIZE; S.base = new SElemType[maxsize]; if (!S.base) exit(1); // 存储分配失败 S.stacksize = maxsize; S.top = 0; // 空栈中元素个数为0 }
bool GetTop(Stack S, ElemType &e) ∥若栈不空,则用e返回S的栈顶元素,并返 回TRUE;否则返回 FALSE if(S top == 0)return FALSE, e=*( s, base+Stop-1);∥返回非空栈 中栈顶元素 return True
• bool GetTop (Stack S, ElemType &e) { // 若栈不空，则用 e 返回S的栈顶元素，并返 回TRUE；否则返回FALSE if (S.top == 0) return FALSE; e = *(S.base + S.top-1); // 返回非空栈 中栈顶元素 return TRUE; }
bool Push(Stack &S, ElemType e) ∥若栈的存储空间不满,则插入元素e为新的 栈顶元素,并返回TRUE;否则返回 FALSE if(stop== s. stacksize)∥栈已满,无 法进行插入 return False (s.base+Stop)=e;∥插入新的元素 ++s top; ∥栈顶指针后移 return True
• bool Push (Stack &S, ElemType e) { // 若栈的存储空间不满，则插入元素 e 为新的 栈顶元素，并返回 TRUE；否则返回 FALSE if (S.top == S.stacksize) // 栈已满，无 法进行插入 return FALSE; *(S.base + S.top) = e; // 插入新的元素 ++S.top; // 栈顶指针后移 return TRUE; }