文档介绍：第三章栈和队列
栈
栈的应用举例
队列
栈与递归的实现
1
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种常用的数据类型
2
学习提要:
,
并能在相应的应用问题中正确选用它们。
,特别应
注意栈满和栈空的条件以及它们的描述方法。
算法,特别注意队满和队空的描述方法。
。
重难点内容:
顺序栈的相关操作、循环队列的判空判满
3
栈(stack)
栈的类型定义
栈的表示和实现
4
栈的定义:限定仅在表尾进行插入或删除操作的线性表。不含元素的空表称空栈。
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
特点:后进先出(LIFO)
栈的类型定义
表尾—栈顶
表头—栈底
5
ADT Stack {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
基本操作:
} ADT Stack
栈的抽象数据类型定义:
6
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit( ))
7
一、顺序栈
栈的表示和实现
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize;
} SqStack;
8
实现:一维数组s[M]
top
1
2
3
4
5
0
进栈Push(&S, e)
A
栈满
B
C
D
E
F
设数组维数为M
top=base,栈空,此时出栈,则下溢(underflow)
top=M,栈满,此时入栈,则上溢(overflow)
top
top
top
top
top
1
2
3
4
5
0
空栈
top
base
base
top
top
出栈
Pop(&S,&e)
1
2
3
4
5
0
A
B
C
D
E
F
top
top
top
top
栈空
base
top
top
栈底指针base,始终指向栈底位置;栈顶指针top,其初值指向栈底,始终在栈顶元素的下一个位置
9
Status InitStack (SqStack &S){
// 构造一个空栈S
=(SElemType*)malloc(STACK_INIT_SIZE*
sizeof(SElemType));
if (!) exit (OVERFLOW); //存储分配失败
= ;
= STACK_INIT_SIZE;
return OK;
}
10