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

第三章栈和队列 3.1栈 栈的定义、栈的存储结构、栈的应用。 3.2队列 队列的定义、队列存储结构、队列的应用。 栈和队列的逻辑结构和物理结构,以及它们之 间的相互关系 定义与之相适应的运算 设计相应的算法 分析算法的效率 1

1 第三章 栈和队列 3.1 栈 栈的定义、栈的存储结构、栈的应用。 队列的定义、队列存储结构、队列的应用。 3.2 队列 栈和队列的逻辑结构和物理结构，以及它们之 间的相互关系 定义与之相适应的运算  设计相应的算法  分析算法的效率

3.1栈(堆栈) 3.1.1栈的定义 栈的概念 (stac)是插入和删除操作限定在一端进行的线性表 多栈的逻辑表示为:S=(a1,a2,,an 栈页tp):表中允许进行插入、删除操作的一端。 栈顶的当前位置是动态变化的)的栈顶的当前位 置由一个称为栈顶指针的位置指示器来指示。 栈底 bottom):表的另一固定端非变化的) 多不含元素的栈称为空 2

2 3.1.1 栈的定义 一. 栈的概念 栈(stack)是插入和删除操作限定在一端进行的线性表。 栈的逻辑表示为：S=(a1 ,a2 ,…an ) 栈顶(top) :表中允许进行插入、删除操作的一端。 栈顶的当前位置是动态(变化的)的,栈顶的当前位 置由一个称为栈顶指针的位置指示器来指示。 栈底(bottom):表的另一固定端(非变化的) 不含元素的栈称为空栈. 3.1 栈（堆栈）

3.1栈(堆栈) 3.1.1栈的定义 栈的概念 多栈的运算特性是后进先出( Last in first out--LIFO) 或先进后出( First in last out--FILO 1234 进栈顺序 出栈顺序 栈顶→ 栈底(固定端) 3N

3 3.1.1 栈的定义 一. 栈的概念 栈的运算特性是后进先出(Last In First Out—LIFO) 或先进后出(First In Last Out—FILO) 3.1 栈（堆栈） 栈底(固定端) 1 2 3 4 栈顶 进栈顺序 出栈顺序

3.1栈(堆栈) 31一个栈的输入序列为abcd,则下列序列中不可 能是栈的输出序列的是( A. bcda B dacb C bcad D. adcb 二.栈的基本运算 多初始化线 nitstack③:构造一个空栈s 多销℃ barTack③)释放栈s占用的存储空间。 求的长度 tackling(.返回栈s中的元素个数。 多判断是否为多cEmp③:若栈s为空,则返回真; 否则返回假。 4

4 例3.1 一个栈的输入序列为abcd ，则下列序列中不可 能是栈的输出序列的是( ) 3.1 栈（堆栈） A. bcda B. dacb C. bcad D. adcb 二. 栈的基本运算 初始化栈InitStack(s):构造一个空栈s。 销毁栈ClearStack(s):释放栈s占用的存储空间。 求栈的长度StackLength(s):返回栈s中的元素个数。 判断栈是否为空StackEmpty(s):若栈s为空,则返回真； 否则返回假

3.1栈(堆栈) 二.栈的基本运算 多进Push③):入栈操作,在栈s顶部插入元素e。 多出Pop(e:出栈函数,若s不空,则返回栈顶元 素并将其值赋给e,然后删除该栈顶元素;否则返 回空元素NULL。 多线页元素Geop(s,)返回当前的栈顶元素,并将 其值赋给与Pop(s,e)函数的差别在不删除栈顶元 素 多显示线中元素 isp Stack(s):从栈顶到栈底顺序显示 栈中所有元素

5 进栈Push(s,e):入栈操作，在栈s顶部插入元素e。 出栈Pop(s,e):出栈函数，若s不空，则返回栈顶元 素并将其值赋给e，然后删除该栈顶元素；否则返 回空元素NULL。 取栈顶元素GetTop(s,e):返回当前的栈顶元素,并将 其值赋给e,与Pop(s,e)函数的差别在不删除栈顶元 素。 显示栈中元素DispStack(s):从栈顶到栈底顺序显示 栈中所有元素。 3.1 栈（堆栈） 二. 栈的基本运算

3.1栈(堆栈) .12栈的顺序存储结构及其基本运算的实现 顺序栈的存储结构描述 舨序栈:即栈的顺序存储结构,是利用一组地址连 续的存储单元(数组)依次存放栈的数据元素。同时 附设指针top指示栈顶元素在顺序栈中的位置。 顺序找的类型定义: f define maxsize 50 typedef int(char,,) Elemtype;如何访问栈顶 typedef struct 元素? ElemType data Sastack *s sI int top;/栈]元置 6 SqStack

6 3.1.2栈的顺序存储结构及其基本运算的实现 顺序栈：即栈的顺序存储结构，是利用一组地址连 续的存储单元（数组）依次存放栈的数据元素。同时 附设指针top指示栈顶元素在顺序栈中的位置。 3.1 栈（堆栈） 一. 顺序栈的存储结构描述 # define MaxSize 50 typedef int(char,…) Elemtype; typedef struct {ElemType data[MaxSize]; int top; //栈顶元素位置 } SqStack; 顺序栈的类型定义： SqStack *s, s1; 如何访问栈顶 元素？

3.1栈(堆栈) 版房的带点 多s->data[表示第计1个进栈的元素 多s>dat>op表示栈顶元素;「"高地址 多当->top=-表示空栈; top c|2 多当s->top= MaxSize-表示栈满 b1 多栈中元素个数或栈的长度为: dataa0低地址 s>top+1。 7

7 3.1 栈（堆栈） s->data[i]表示第i+1个进栈的元素； s->data[s->top]表示栈顶元素； 当s->top=-1表示空栈； 当s->top=MaxSize-1表示栈满； 顺序栈的特点： data top 低地址 高地址 0 1 2 n s a b c d 栈中元素个数或栈的长度为： s->top＋1

3,1栈(堆栈) 顺序栈的基本运算 ●始化线 Initstack(s) 建立一个新的空栈s,实际上是将栈顶指针指向-1即可 void Initstack(sqstack *&s) 0钱5进行初始化 s=( Sqstack2) malloc( sizeof( Sqstack);顺序栈s S->top=-1; Maxsize 空栈 top 栈底

8 二. 顺序栈的基本运算 ⚫初始化栈InitStack(s) void InitStack(SqStack *&s) { //对栈s进行初始化 s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } 建立一个新的空栈s,实际上是将栈顶指针指向-1即可。 top -1 栈底 0 1 2 … MaxSize-1 顺序栈s 空栈 3.1 栈（堆栈）

3,1栈(堆栈) 顺序栈的基本运算 销毁线 Clearstack(s) void Clearstack( sqStack *&s) free(s) 顺序栈s 求的长度 tacklength(③) MaxSize-1 int StackLength(sqstack *s top→2 return(s->top+1) 1栈底 9

9 二. 顺序栈的基本运算 ⚫销毁栈ClearStack(s) void ClearStack(SqStack *&s) { free(s); } int StackLength(SqStack *s) { return(s->top+1); } ⚫ 求栈的长度StackLength(s) top -1 栈底 0 1 2 … MaxSize-1 顺序栈s 3.1 栈（堆栈）

3,1栈(堆栈) 顺序栈的基本运算 兴等为会CEmy() Sta aStac return(s->top==-1) 显示线中元素 Disp Stack③ void Dispstack( sqstack *s) 从栈顶到栈底顺序显示栈中所有元素。 int 1; for〔i=s>top;i>=0;i printf("%oc", s->datai printf("in") 10

10 二. 顺序栈的基本运算 ⚫判断栈是否为空StackEmpty(s) int StackEmpty(SqStack *s) { return(s->top==-1); } ⚫ 显示栈中元素DispStack(s) void DispStack(SqStack *s) {//从栈顶到栈底顺序显示栈中所有元素。 int i; for (i=s->top;i>=0;i--) printf("%c ",s->data[i]); printf("\n"); } 3.1 栈（堆栈）