《数据结构》课程教学资源：第四章 栈和队列

答是要 4.1 °顺序找 °链式栈 °找的应用 4.2栈和递归的实现 °基本概念 基本问题 4.3队列 饭序队列 °链式队列 °从列的应用 4.4栈和队列的应用范例

内容提要 4.1 栈 • 顺序栈 • 链式栈 • 栈的应用 4.2 栈和递归的实现 • 基本概念 • 基本问题 4.3 队列 • 顺序队列 • 链式队列 • 队列的应用 4.4 栈和队列的应用范例

41传 1、定义 栈( Stack):一种后进先出(L|FO的线性表 向栈中插入和删除元素,必须在栈的 端进行。因此,栈是操作受限的! 栈顶top):元许插入和删除的一端 栈底( bottom:不允许插入和删除的一端 栈的主要操作: 建立空栈 进线 出栈 判断栈是否空 判断栈是否满获取栈顶元素值

4.1 栈 1、定义 栈(Stack)：一种后进先出(LIFO)的线性表。 栈顶(top)：允许插入和删除的一端 栈底(bottom)：不允许插入和删除的一端 栈的主要操作： 建立空栈 进栈 出栈 判断栈是否空 判断栈是否满 获取栈顶元素值 向栈中插入和删 除元素，必须在栈的一 端进行。因此，栈是操作受限的！

出栈 进栈 栈的修改是按后进先出 栈顶 an Last In First Out,简称 a2 a1 L|FO的原则进行的 栈的示意图

栈(cont’d) a1 a2 … an 出栈 进栈 栈顶 栈的示意图 栈的修改是按后进先出 (Last In First Out，简称 LIFO)的原则进行的

传之顺序线 2、版序:用版序表实现的线 (1)顺序的数据类型定义: #define maXsize 50 typedef struct elemtype elem MAXSIE: int top /*栈顶*/ JSQSTACK

栈之顺序栈 2、顺序栈：用顺序表实现的栈 (1) 顺序栈的数据类型定义： #define MAXSIZE 50 typedef struct { elemtype elem[MAXSIZE]; int top; /*栈顶*/ }SQSTACK;

之顺序c( (2)顺序线的基本操作(建线: 建立空栈 void initstack(SQSTACK *s s→>top=-1;/*-1表示空栈*

栈之顺序栈(cont’d) (2) 顺序栈的基本操作(建栈)： void initstack(SQSTACK *s) { s→top= -1; /*-1表示空栈*/ } • 建立空栈

之顺序( (3)顺序线的基本操作(判的 判断栈是否空 int stackempty(sQsTACK S return s top==-1;

栈之顺序栈(cont’d) (3) 顺序栈的基本操作(判断)： int stackempty(SQSTACK s) { return s.top == -1; } • 判断栈是否空

之顺序c( (4)顺序找的基本操作入线: 入栈 int push( SQSTACK“s, elemtype e) f(s→)top= MAXSIZE-1) return0;体栈满,入栈失败* S→>top++; s→>lem|s→>topl=e; return 1

栈之顺序栈(cont’d) (4) 顺序栈的基本操作(入栈)： int push(SQSTACK *s, elemtype e) { if(s→top==MAXSIZE-1) return 0; /*栈满,入栈失败*/ s→top++; s→elem[s→top]=e; return 1; } • 入栈

之顺序c( 5)顺序线的基本操出线: 出栈 int pop(sQsTACK *s, elemtype if(s→>top=1) return0;*栈空,出栈失败* e=s→> elems→)topl; →)top-; eturn 1

栈之顺序栈(cont’d) (5) 顺序栈的基本操作(出栈)： int pop(SQSTACK *s, elemtype *e) { if(s→top==-1) return 0; /*栈空,出栈失败*/ *e=s→elem[s→top]; s→top--; return 1; } • 出栈

之顺序c( (6)顺序线的基本操作获取 获取栈顶值 int gettop(SQSTACK S, elemtype *e) if(s-top==-Dreturn 0; e=s→> elem s→>topl;

栈之顺序栈(cont’d) (6) 顺序栈的基本操作(获取)： int gettop(SQSTACK s,elemtype *e) { if(s→top==-1)return 0; *e=s→elem[s→top]; } • 获取栈顶值

传之链式线 3、链式:用链表实现的线 (1)链式线的数据类型定义(与链表相同): typedef struct node elemtype data struct node *next: JNODE, NODEPTR, * LKSTACK; #define len sizeof(Node

栈之链式栈 3、链式栈：用链表实现的栈 (1) 链式栈的数据类型定义（与链表相同）： typedef struct node { elemtype data; struct node *next; }NODE ,*NODEPTR, *LKSTACK; #define LEN sizeof(NODE)