第4章栈和队列 4.1栈的基本概念 4.2栈的表示与实现 4.3栈的应用 4.4队列的基本概念 4.5队列表示与实现 4.6队列的应用 4.7递归及其应用 2021/1/29 数据结构及其算法第4章栈和队列
第4章 栈和队列 •4.1 栈的基本概念 •4.2 栈的表示与实现 •4.3 栈的应用 •4.4 队列的基本概念 •4.5 队列表示与实现 •4.6 队列的应用 •4.7 递归及其应用 2021/1/29 数据结构及其算法 第4章 栈和队列 2
4.1栈的基本概念 栈( stack):限定仅在表尾进行插入或删除操作的 线性表 从数据结构角度看,栈也是线性表,或操作受限的 线性表,称为限定性数据结构 Data structure (D,S) ·从抽象数据类型角度看,允许的操作不一样,则数 据类型不同 °ADT=( DSP) 2021/1/29 数据结构及其算法第4章栈和队列
4.1 栈的基本概念 •栈(stack)：限定仅在表尾进行插入或删除操作的 线性表 •从数据结构角度看，栈也是线性表，或操作受限的 线性表，称为限定性数据结构 •Data_Structure = (D,S) •从抽象数据类型角度看，允许的操作不一样，则数 据类型不同 •ADT = (D,S,P) 2021/1/29 数据结构及其算法 第4章 栈和队列 3
设栈=(a1ra2 a a1称为栈底( bottom)元素 a称为栈顶(top)元素 出栈栈 栈顶插入元素-入栈 栈顶删除元素-出栈 栈顶 后进先出(1 ast in first out l工FO a 栈底 a 詹天佑设计的人字形铁路 (北京青龙桥车站附近) 2021/1/29 数据结构及其算法第4章栈和队列
•设栈S = (a1,a2,...,an) • a1称为栈底(bottom)元素 • an称为栈顶(top)元素 •栈顶插入元素 – 入栈 •栈顶删除元素 – 出栈 •后进先出(last in first out, LIFO) 2021/1/29 数据结构及其算法 第4章 栈和队列 4 a1 a2 an … 栈顶 栈底 出栈 入栈 詹天佑设计的人字形铁路 （北京青龙桥车站附近）
42栈的表示与实现 顺序栈:栈的顺序存储结构 类似顺序表 由于总在栈顶插入、删除,保留栈顶位置方便操作 typedef struct i ElemType*elem;//基地址 int stacksize; /当前分配内存大小,单位是 sizeof( ELem Type) int top, /栈顶位置,定义为表长-1 SqStack 2021/1/29 数据结构及其算法第4章栈和队列
4.2 栈的表示与实现 •顺序栈：栈的顺序存储结构 • 类似顺序表 • 由于总在栈顶插入、删除，保留栈顶位置方便操作 2021/1/29 数据结构及其算法 第4章 栈和队列 5 typedef struct { ElemType *elem; // 基地址 int stacksize; // 当前分配内存大小，单位是sizeof(ElemType) int top; // 栈顶位置，定义为表长-1 } SqStack;
顺序栈基本操作的实现(算法4.1~4.3) void Initstack sq( sqstack &S, int size)t Selem= new ElemType[size]; s. stacksize maize s top =-1, void Destroystack sq(Sqstack &s)i delete [selem; s. stacksize =0: S top bool GetTop sq( SqStack S, ElemType &e)i if (s top ==-1) return false; e selem[s top return true 2021/1/29 数据结构及其算法第4章栈和队列
•顺序栈基本操作的实现（算法4.1~4.3） 2021/1/29 数据结构及其算法 第4章 栈和队列 6 void InitStack_sq(SqStack &S, int msize) { S.elem = new ElemType[msize]; S.stacksize = msize; S.top = -1; } void DestroyStack_sq(SqStack &S) { delete []S.elem; S.stacksize = 0; S.top = -1; } bool GetTop_sq(SqStack S, ElemType &e) { if (S.top == -1) return false; e = S.elem[S.top]; return true; }