数据结构第3章第3章栈和队列栈和队列是两种重要的线性结构。线性表栈队列
Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+
1Delete(L,i)Delete(S,n)Delete(Q,1)1≤
i≤n从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表；
从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。3.1栈1.抽象数据类型栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。对于栈而言，表尾端有其特殊含义，称为栈顶（Top），表头端称为栈底（Bott
om）。不含元素的空表称为空栈。设栈S＝（a1,a2,……an),
栈中元素按a1,a2,……an的次序进栈，出栈是按an,an-1,……,a2,a1的次序。栈的
特性是按后进先出的原则进行的，因此，栈是后进先出的线性表。想一想：生活中有哪些例子类似于栈？计算机中有哪些问题应用栈？
摞盘子函数递归调用栈底元素:?，栈顶元素:?。a1an如何理解”后进先出”?
“后进先出”例:一个栈的入栈序
列是A，B，C，D，E，入栈和出栈操作可交替进行，则栈的不可能的输出序列是________。A)
A，B，C，D，EB)D，C，E，A，BC)E，D，C，B，AD)C，B，A，D，EB
栈的抽象数据类型的定义：ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...
,n,n≥0}数据关系：R1＝{|ai-1,ai∈D,i=2,...
,n}约定an端为栈顶，a1端为栈底。
基本操作：InitStack(&S)DestroyStack(&S)
StackLength(S)StackEmpty(s)GetTop(S,&e)ClearSt
ack(&S)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())
2.栈的表示与实现栈有两种存储表示：顺序栈和链栈。顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶
的数据元素。在初始化空栈时，先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。当top＝bas
e时，表示为空栈。插入元素叫入栈，删除元素叫出栈。当插入新栈顶元素时，指针top增1。
低高地址topbase空栈入栈出栈a1a3topa
2a4toptoptopa4a4当删除栈顶元素时，指针top减1。非空栈中的栈顶指针始终在栈顶元素
的前一个位置上。top//-----栈的顺序存储表示-----#defineSTACK_INIT_
SIZE100;#defineSTACKINCREMENT10;typedefstruct{
}SqStack;SqStackS;SElemTypebase;SElem
Typetop;intstacksize;基本操作的算法描述：（1）初始化一个栈StatusIni
tStack(SqStack&S){//构造一个空栈SS.base=(ElemType)malloc(STACK_
INIT_SIZE
sizeof(ElemT
ype));if(!S.base)return(OVERFLOW);//存储分配失败S.top=S.b
ase;S.stacksize=STACK_INIT_SIZE;returnOK;}
（2）取栈顶元素StatusGetTop(SqStack
S,SElemType&e){//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERRORif
(S.top==S.base)returnERROR;e=(S.top-1));returnOK;}
(3)入栈StatusPush
(SqStack&S,SElemTypee)if(S.top-S.base>=S.stacksize)
//栈满，追加存储空间S.base=(ElemType)realloc(S.base,
(S.stacksize+STACKINCREMENT)sizeof(ElemT
ype));if(!S.base)return(OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;S.stacksize+=STACKINC
REMENT;S.top++=e;returnOK;}}{第一步:判断栈是否满？若已满，
则追加空间，否则，进入第二步。{第二步:往s.top指针处插入元素e，然后s.top指针加1。(3)出栈
StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，
//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)ret
urnERROR;e=--S.top;returnOK;}
第一步:判断栈是否为空？若空，则返回ERROR，否则，进入第二步。第二步:将
s.top指针减1，然后将s.top指针所指的元素赋给变量e。3.2栈的应用数制转换算法基于原理：N
=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：
计算顺序输出顺序NNdiv8
Nmod813481684168210
2125202void
conversion(){//对于输入的任意一个非负十进制整数，打印//输出与其等值的八进制数InitS
tack(S);scanf("%d",N);while(？){Push(S,
N%8);N=N/8;}while(!StackEmpty(S)){
Pop(S,e);printf("%d",e);}}//conversion
NS.top!=S.base作业①若一个栈的
输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。A不确定Bn-ICn-
i-1Dn-i+1②一个栈的入栈序列是a，b，1，5，6，则栈的不可能的输出序列是________。A)
6，5，1，b，aB)6，a，b，5，1C)1，b，a，5，6D)5，1，b，
a，6
预习：3.
4.1节和3.4.3实验作业：①用C或C++编程实现创建一个栈，在栈中压入一个元素，并弹出一个元素。②编程实现将任一个非
负十进制整数转换成其等值的八进制数。数据结构第3章 |
|
