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