第三章 栈和队列栈和队列是操作受限的线性表，它们的基本操作是线性表操作的子集。栈是限定仅在表尾进行插入或删除操作的线性表。表尾端成为栈顶，表头端成为栈底。栈的修改是按后进先出的原则进行，栈又称为后进先出的线性表。栈和队列的示意图栈只能在栈顶进行插入删除等操作，按照后进先出的原则。a1a2an.栈顶栈顶栈底栈底进栈进栈出栈出栈a1a2a3an. . .出队列出队列入队列入队列队队头头队队尾尾队列：队尾进行插入操作，队头进行删除操作。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型栈、队列与线性表的插入、删除操作对比3.1 栈的类型定义栈的类型定义3.3 栈的应用举例栈的应用举例3.2 栈的表示与实现栈的表示与实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现3.1 栈的类型定义栈的类型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则FALE。 StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新 的栈顶元素。a1a2ane Pop(&S, &e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 栈的存储方法栈的存储方法顺序栈：利用一组地址连续的 存储单元依次存放自栈底到栈 顶的数据元素，同时附设指针 top指示栈顶元素在顺序栈中的 位置。链栈：头指针指向栈顶元素，每个结点的指针域指向前一个结点。basetopABC栈顶指针a1anan-1顺顺 序序 栈栈top:栈顶指针，始终指向栈顶元素的下一个位置。栈顶指针，始终指向栈顶元素的下一个位置。base：栈底指针，始终指向栈底的位置，：栈底指针，始终指向栈底的位置，baseNULL，栈不存在。，栈不存在。base=top，栈空。，栈空。basetopbasetopbasetopABCABCDEF链栈链栈注意注意: 链栈中链栈中指针的方向指针的方向topa1anan-1链栈是动态分配元素存储空间，链栈是动态分配元素存储空间，链栈是动态分配元素存储空间，链栈是动态分配元素存储空间，元素的插入删除操作都是在表元素的插入删除操作都是在表元素的插入删除操作都是在表元素的插入删除操作都是在表的同一端进行，头指针就是栈的同一端进行，头指针就是栈的同一端进行，头指针就是栈的同一端进行，头指针就是栈顶指针。顶指针。顶指针。顶指针。栈顶栈顶栈底栈底3.2 栈的表示和实现栈的表示和实现栈的定义栈的几个基本操作的实现Status InitStack (SqStack &S)Status Push (SqStack &S, SElemType e)Status Pop (SqStack &S, SElemType &e)/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; /构造栈之前和销毁栈之后，构造栈之前和销毁栈之后，base值为值为NULL SElemType *top; /栈顶指针 int stacksize; /当前已分配的存储空间，以元素为单位 SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 Status InitStack (SqStack &S) / 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;ababcs.bases.tops.bases.topStatus Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;ABCs.bases.top ABCs.bases.tope