栈的特点 栈顶：对栈进行操作的一端。 后进先出(LIFO) 栈顶指针：指示栈顶位置的指 入栈 出栈 针。 栈的长度：栈中元素的个数。 栈顶 An 假设栈S-(a1,a2,a3,,an), an-1 则a1称为栈底元素，a为栈顶 元素。插入的过程称为入栈， a2 删除的过程称为出栈。 栈底 a1 ◆栈称为后进先出表(LIFO)。 栈的示意图
◆ 栈顶：对栈进行操作的一端。 ◆ 栈顶指针：指示栈顶位置的指 针。 ◆ 栈的长度：栈中元素的个数。 ◆ 假设栈S=(a1 , a2 , a3 , …,, an )， 则a1称为栈底元素，an为栈顶 元素。插入的过程称为入栈， 删除的过程称为出栈。 ◆ 栈称为后进先出表（LIFO）。 an an-1 … a2 a1 入栈 出栈 栈顶 栈底 栈的示意图 栈的特点 后进先出(LIFO)
>栈的示意图 栈的特点 出栈 后进先出 进栈 (LIFO) 栈顶 an-1 第一个进栈的元素在栈底： 最后一个进栈的元素在栈顶： a2 栈底 aj 第一个出栈的元素为栈顶元素； 最后一个出栈的元素为栈底元素
➢ 栈的示意图 an an-1 … a2 a1 栈顶 栈底 出栈 进栈 第一个进栈的元素在栈底； 最后一个进栈的元素在栈顶； 第一个出栈的元素为栈顶元素； 最后一个出栈的元素为栈底元素。 栈的特点 后进先出 （LIFO）
抽象数据类型栈的定义： ADT Stack 数据对象： D=a ai EElemSet,i=1,2,...,n,n20 数据关系： R1={<a-l,a:>la-1,a∈D,i=2,,n} 约定a端为栈顶，a1端为栈底。 基本操作： ADT Stack
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 端为栈底。 基本操作： } ADT Stack 抽象数据类型栈的定义:
栈的基本操作： InitStack(&S) DestroyStack() StackEmpty(s) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,&e)
InitStack(&S) ClearStack(&S) StackEmpty(s) GetTop(S, &e) Push(&S, e) Pop(&S, &e) 栈的基本操作: DestroyStack(&S)
InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁
InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁