数据结构栈和队列课件.ppt

该【数据结构栈和队列课件 】是由【7489238】上传分享，文档一共【45】页，该文档可以免费在线阅读，需要了解更多关于【数据结构栈和队列课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构课程的内容
栈（Stack）
1
队列（Queue）
2
定义
逻辑结构
存储结构
运算规则
实现方式
3
定义
逻辑结构
存储结构
运算规则
实现方式
4
第三章 栈和队列
1. 定义
栈
与同线性表相同，仍为一对一关系。
用顺序栈或链栈存储均可，但以顺序栈更常见
只能在栈顶(表尾)运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。
关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。
基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。
3. 存储结构
4. 运算规则
5. 实现方式
2. 逻辑结构
限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）
栈
问：堆栈是什么？它与一般线性表有什么不同？
答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。
与一般线性表的区别：仅在于运算规则不同。
一般线性表 堆栈
逻辑结构：一对一 逻辑结构：一对一
存储结构：顺序表、链表 存储结构：顺序栈、链栈
运算规则：随机存取 运算规则：后进先出(LIFO)
“进” ＝压入=PUSH（x)
“出” ＝弹出=POP ( y )
01
栈 是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base
02
例如： 栈 s= (a1 , a2 , a3 , ……….,an-1 , an )
03
a1 称为 栈底元素 an 称为 栈顶元素
04
插入元素到栈顶（即表尾）的操作，称为入栈。
从栈顶（即表尾）删除最后一个元素的操作，称为出栈。
05
强调：插入和删除都只能在表的一端（栈顶）进行！
教材P44对栈有更详细定义：
顺序栈示意图
s
a1
a2
a3
data
a4
(栈底)
(栈顶)
99
.
.
.
3
2
1
0
top
a1
a2
……
an
顺序栈S
ai
……
表和栈的操作区别——对线性表 s= (a1 , a2 , …. , an-1 , an )
表头
表尾
栈底base
栈顶top
低地址
高地址
写入：v[i]= ai
读出： x= v[i]
压入：PUSH (an+1)
弹出： POP (x)
前提：一定要预设栈顶指针top！
低地址
高地址
v[i]
a1
a2
ai
an
……
顺序表V[n]
……
an+1
入栈操作——例如用堆栈存放（A，B，C，D） （注意要遵循“后进先出” 原则）
A
A
C
B
A
B
A
top
核心语句：
top=L;
顺序栈中的PUSH函数
status Push(ElemType x)
{ if(top>M){上溢}
else v[top++]=x;
}
Push (B);
Push (C);
Push (D);
top
top
top
top
低地址L
Push (A);
高地址M
B
C
D
出栈操作——例如从栈中取出‘B’ （注意要遵循“后进先出” 原则）
D
C
B
A
top
top
D
C
A
B
D
C
B
A
top
D
C
B
A
top
低地址L
高地址M
D
核心语句：
Pop ( );
Pop ( );
Printf( Pop () );
顺序栈中的POP函数
status Pop( )
{ if(top=L) { 下溢 }
else { y=v[--top]; return(y);}
}
01
02
03
04
例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？
435612中到了12顺序不能实现；
135426可以实现。
05
答：
43512不可能实现，主要是其中的12顺序不能实现；
12345的输出可以实现，只需压入一个立即弹出一个即可。
例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？
答：
06