文档介绍：第三章栈和队列
数据结构
1
栈的组织和基本运算
队列的组织和基本运算
栈是“后进先出”的线性表
队列是“先进先出”的线性表
栈的应用
递归算法
2
栈(Stact): 限定只能在表尾的一端进行插入和删除的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(TOP):允许插入和删除的一端。
栈底(BOTTOM):不允许插入和删除的一端。
栈的定义和运算
栈顶 an
┇
┇
a2
栈底 a1
进栈
出栈
3
问题:如果进栈顺序为1,2,3,4,5,6;不限制出栈的时间,问能否得到则下面的出栈顺序。
(1) 4,3,5,6,1,2;
(2) 1,3,5,4,2,6;
(1)
①in
②in
③in
④in
④out
③out
⑤in
⑥in
⑤ out
⑥ out
4
对栈进行的基本运算有:设s是栈
(1) INITSTACK (s):设置一个空栈s。
(2) STACKEMPTY (s) : 判断s是否是空栈。
如果栈空返回1,非空返回0。
(3) PUSH (s ,x):入栈操作;
在栈s中插入一个新的栈顶元素x。
(4) POP (s) :出栈函数;删除栈顶元素。
(5) GETTOP (s) :读取栈顶元素。
若栈为空,返回空值。
5
设一个数组:
elem[arrmax]
(2) 设整型变量top指示栈顶位置。称top为栈顶指针。
elem[arrmax]
arrmax-1
┆
┆
2 a3 top
1 a2
0 a1
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
栈的存储结构和基本运算的实现
其中, arrmax指示栈的当
前可使用的最大容量。 Top为
栈顶指针,当用一维数组作为
栈的存储空间时,s->top=-1
表示空栈;每当插入新元素,
指针top加1,删除栈顶元素时,
指针top减1。非空栈中,top
始终指向栈顶元素。
6
(1) top = = -1: 空栈;
(2) top>=0: elem[0]为栈底元素,s[top]为栈顶元素;
(3) top= = 0: elem[0]既是栈底元素,也是栈顶元素
(4) top= = arrmax-1为栈满
3
2 c top
1 b
0 a
elem[arrmax]
arrmax-1
7
1. 顺序栈结构的定义
# define MAXLEN 栈可能达到的最大长度
typedef struct {
ElemType elem[MAXLEN] ; // 数组空间
int top ;
} SqStack ;
SqStack s;
8
栈的初始化
SqStack Init_Stack(void)
{ SqStack S ;
==0 ; return(S) ;
}
9
2 栈的初始化
Status Init_Stack(void)
{ SqStack S ;
=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));
if (! ) return ERROR;
= ; /* 栈空时栈顶和栈底指针相同*/
S. stacksize=STACK_SIZE;
return OK ;
}
10