(13)--第三章第一节栈和队列的特点.pdf

01【栈的概念】

目录02【栈的特点】

CONTENTS03【队列的概念】

04【队列的特点】

01栈的概念

栈的概念

假设死胡同的宽走进死胡同的5人

度恰好只够一个人要按相反次序退出

死胡同就是一个栈！

栈的概念PushPop

Topaann

允许进行插入、删除…

操作的表尾端称为栈栈的删除操作通

顶，表头端称为栈底常称为退栈或出栈a

Bottom1

栈顶、栈底出栈/退栈

栈进栈/入栈空栈

限定仅在表尾进行插栈的插入操作通丌含元素的

入和删除操作的线性表常称为进栈或入栈空表称为空栈

栈的概念

栈的抽象数据类型＝逻辑结构＋基本运算

ADTStack{

数据对象：

D＝{a|a∈ElemSet,i=1,2,...,n,n≥0}

ii

数据关系：

R1＝{a,a|a,a∈D,i=2,...,n}

i-1ii-1i

约定an端为栈顶，a1端为栈底

基本操作：

}ADTStack

栈的概念

基本操作：

InitStack(S):初始化栈，构造一个空栈S

。

DestroyStack(S)：销毁栈。释放S占用的存储空间。

StackLength(S)：返回栈S的元素个数，即栈的长度。

StackEmpty(S)：判断栈S是否为空，若为空返回真，否则返回假。

GetTop(S,e)：取栈S的栈顶元素，用e返回值。

ClearStack(S)：将S清为空栈。

Push(S,e)：进栈，插入元素e作为新的栈顶元素。

Pop(S,e)：出栈，删除栈S的栈顶元素，用e返回其值。

StackTravers(S,visit())对栈中的元素进行遍历。

02栈的特点

栈的特点

后进先出(LIFO)

例子：设栈S的初始状态为元素e1,e2,e3,e4,按此顺序依次通过

栈S（假设元素可以在任何时刻出栈）,下列的出栈序列是否

是可能的？

A.e4,e3,e2,e1e3e4