《数据结构》课程PPT教学课件（2015）第3章 栈和队列（上）

《数据结构》 第三章栈和队列（上）

《 数据结构》 (上)

第三章 栈和队列 数据结构 3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例 3.2.1数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解 3.2.5表达式求值 3.3栈与递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列一队列的链式表示和实现 3.4.3 循环队列一队列的顺序表示和实现

数据结构

3.1栈 数据结构 3.1.1抽象数据类型栈的定义 栈(Stack)是限制在表的一端进行插入和删除 运算的线性表，通常称插入、删除的这一端为栈顶 (Top),另一端为栈底(Bottom)。当表中没有 元素时称为空栈。 假设栈S=(a1,a2,a3,an),则a1称为 栈底元素，an为栈顶元素。栈中元素按a1,a2, a3,an的次序进栈，退栈的第一个元素应为栈 顶元素

数据结构

数据结构 例、一叠书或一叠盘子。 栈顶 a n a n-1 特点：后进先出 (LIFO)。 a2 栈底 a1 栈的ADT定义参见p45

数据结构

数据结构 3.1.2栈的表示和实现 一、 顺序栈 由于栈是操作受限的线性表，因此线性表的存 储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，可用数组来 实现顺序栈。因为栈底位置是固定不变的，所以可 以将栈底位置设置在数组的两端的任何一个端点。 栈顶位置是随着进栈和退栈操作而变化，故需 用一个指针top来指示当前栈顶的位置，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将 顺序表的类型定义中的长度属性改为top指针即可

数据结构

数据结构 顺序栈的类型定义如下： #define STACK INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; }SqStack;

数据结构

数据结构 当栈满时再做进栈运算必定产生空间溢出，简 称“上溢”，当栈空时再做退栈运算也将产生溢 出，简称“下溢”。溢出是一种出错状态，应 该设法避免。 栈的几个常用的基本操作的实现： 1、栈的初始化InitStack操作(P47) 2、进栈Push操作(P47) 3、出栈Pop操作(P47) 4、取栈顶元素GetTop操作（P47)

数据结构

数据结构 链栈 栈的链式存储结构称为链栈，它是操作受限的 单链表，其插入和删除操作仅限制在表头位置 上进行。链栈通常用不带头结点的单链表来实 现。栈顶指针就是链表的头指针。 链栈的类型说明如下： typedef struct SNode { SElemType data; struct SNode *next; }SNode,*LinkStack;

数据结构

数据猪构 1、进栈操作的实现： 栈底 7 void Push_LS(LinkStack &S,SElemType e) { p=(LinkStack)malloc(sizeof(SNode)); p->data=e; p->next=S; S=p;

数据结构 . ^ 栈底 S S e p

数据结构 2、退栈操作的实现： X大 栈底 Status Pop_LS(LinkStack &S,SElemType &e) { if(S==NULL)return ERROR; e=S->data; p=S; S=S->next; free(p);

数据结构 S . ^ 栈底 S p