济南大学数据结构 第三章.ppt

济南大学数据结构 第三章.ppt第三章栈和队列
栈和队列是两种重要的线性结构
栈和队列是操作受限的线性表
出
进
排队买票
羊肉串
出
如何理解?
进
栈
队列
栈
栈的定义
栈是限定仅在表尾(栈顶)进行插入或删除操作的线性表。
通常,表头端称为栈底,表尾端称为栈顶。
出栈
进栈
a1为栈底元素
an为栈顶元素
按a1、a2…、an顺序进栈
按an…、 a2、a1顺序出栈
进栈、出栈均在表尾(栈顶)进行
a1
a2
an
. . .
表头
表尾
栈底
栈顶
栈称为后进先出线性表(LIFO)
栈的抽象数据类型的定义
InitStack( &S )
结果: 构造一个空栈 S。
数据对象: D = { ai | ai ∈ElemSet,i = 1, 2, …, n }
数据关系: R1 = { < ai-1, ai > } ;约定a1为栈底,an为栈顶。
基本操作:
ADT Stack {
} ADT Stack
DestroyStack( &S )
结果: 销毁栈 S。
条件: 栈 S 已存在。
…
主要基本操作包括:
StackIsEmpty ( S )
StackLength ( S )
GetTop ( S,&e )
Push ( &S,e )
Pop ( &S,&e )
StackTraverse ( S,visit() )
ClearStack( &S )
区别?
栈的表示和实现
1. 顺序栈
顺序栈;链式栈。
base
top
栈底指针——base
栈顶指针——top
取决于数据在计算机中存储方式!
A
B
C
栈容量
注意!
指向栈底元素
指向栈顶元素的下一个元素
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
typedef struct {
SElemType * base ;
SElemType * top ;
int stacksize ;
} SqStack ;
三元组
SqStack S ;



*
*
空栈
A
B
C


D
E
满栈


如何判定?
==
A
B
C


栈中有三个元素
SqStack S
如何判定?
- ==
= ( SElemType * ) malloc
( STACK_INIT_SIZE * sizeof(SElemType) );
if ( ! ) exit(OVERFLOW) ;
= ;
= STACK_INIT_SIZE ;
return OK ;
Status InitStack ( SqStack &S ) {
}
栈的初始化
=
初始化为一个空栈
. . . . . .
100
取栈顶元素
if ( == ) return ERROR ; //空栈
e = * ( – 1 ) ;
return OK ;
Status GetTop ( SqStack S ,SElemType &e ) {
}
A
B
C


- 1