文档介绍：数据结构课程的内容
数据结构
逻辑结构
存储(物理)结构
数据运算
线性结构
非线性结构
顺序存储结构
链式存储结构
插入运算
删除运算
修改运算
查找运算
排序运算
树形结构
图状结构
线性表、栈、队列、串、数组
3/19/2018
1
第3章栈和队列
F 栈
F 栈的应用举例
F 队列
3/19/2018
2
栈
一、栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。
表尾称为栈顶top;
表头称为栈底bottom;
例:栈S=(a1,a2,……,an-1 ,an)
栈顶
栈底
入栈:在栈顶插入一个元素的操作;
特点:后进先出/LIFO
出栈:从栈顶删除一个元素的操作;
基本操作:在栈顶进行插入、删除、栈的初始化、
判空及取栈顶元素
3/19/2018
3
栈
二、栈的表示和实现
1、栈的顺序存储结构(顺序栈)
是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
设定常量:STACK_INIT_SIZE 存储空间初始分配量
STACKINCREMENT 存储空间分配增量
栈的数据类型定义:
typedef struct {
SElemType *base;
SElemType * top;
int stacksize;
}SqStack;
3/19/2018
4
base
base为栈底指针,始终指向栈底,base=NULL表示栈结构不存在;
top为栈顶指针,初值指向栈底,
top
入栈:插入新的栈顶元素,指针top加1---先插入后加1
A
即top=base,表示栈空。
B
C
D
出栈:指针top减1,删除栈顶元素---先减1后删除
非空栈的栈顶指针top始终指向栈顶元素的下一个位置
栈
E
F
top
top
top
栈满
top-base=stacksize
base
top
A
B
C
D
E
F
top
top
top
top
top
top
栈空
入栈PUSH(s,x):s[top++]=x;
出栈 POP(s,x):x=s[--top];
3/19/2018
5
栈
例1:一个栈的输入序列为1,2,3,若在入栈的过程中
允许出栈,则可能得到的出栈序列是什么?
答:
可以通过穷举所有可能性来求解:
① 1入1出, 2入2出,3入3出, 即123;
② 1入1出, 2、3入,3、2出, 即132;
③ 1、2入,2出, 3入3出, 即231;
④ 1、2入,2、1出,3入3出, 即213;
⑤ 1、2、3入,3、2、1出, 即321;
合计有5种可能性。
3/19/2018
6
栈
例2:一个栈的输入序列是12345,若在入栈的过程
中允许出栈,则栈的输出序列43512可能实现
吗?12345的输出呢?
例3:设依次进入一个栈的元素序列为c,a,b,d,
则可得到出栈的元素序列是:
A)a,b,c,d B)c,d,a,b
C)b,c,d,a D)a,c,d,b
若输入序列是…,Pj…Pk…Pi …(Pj<Pk<Pi) ,一定不存在这样的输出序列…,Pi…Pj…Pk …
即对于输入序列1,2,3,不存在输出序列3,1,2
3/19/2018
7
栈
2、栈的链式存储结构
an
an-1
an-2
a1 ∧
S
base
top
数制转换(十转N)
括号的匹配
表达式求值
汉诺塔
栈也可以用链式结构来表示,用链式结构来表示的栈就是链栈
链栈的构造方式——以头指针为栈顶,在头指针处插入或删除.
链栈中每个结点定义为:
typedef Struct SNode{
SElemType data;
Struct SNode * next;
} SNode;
3/19/2018
8
栈的应用举例
一、数制的转换
例: (1024)10=( )8
1024
8
128
0
8
16
0
8
2
0
8
0
2
2000
余数
商
void conversion( )
{
InitStack(S);
scanf(“%d”,N);
while(N)
{
Push(S,N%8);/*余数压栈*/
N=N/8;
}
while(!StackEmpty(S))
{
Pop(S,e); /*出栈*/
Printf(“%d”,e);
}
}
3/19/2018
9
栈的应用举例
二、表达式求