数据结构--第三章 栈和队列.ppt

文档介绍：[内容提要]
第三章栈和队列
1



2
定义:栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表,简称LIFO线性表。
允许进行插入和删除的一端称为栈顶(top)
不允许插入和删除的一端称为栈底(bottom)
不含元素的空表称为空栈。
特点:后进先出(LIFO)或先进后出(FILO)
栈的基本概念
3
栈的示例图
a1
a2
a3
an
栈顶(top)
栈底(bottom)
进栈
出栈
1
2
3
4
5
进
出
4
用除法把十进制数转换成二进制数,把所有的余数按出现的逆序排列起来(先出现的余数排在后面,后出现的余数排在前面),十进制数35转换成二进制数
35
17
8
4
2
1
0
1
1
0
0
1
余数
结果:10011
例:
5
栈的顺序存储结构(顺序栈)
顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素,通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置或后一空位置(下标)。
顺序栈的类型说明:
#define maxsize 100
typedef struct
{
elemtype elem[maxsize];
int top;
}sqstacktp;
6
base
1
2
3
4
5
0
栈空
栈顶指针top,指向实际栈顶后的空位置.
top
1
2
3
4
5
0
进栈
A
top
出栈
栈满
B
C
D
E
F
设数组维数为maxsize
=0,栈空,此时出栈,则下溢
= maxsize,栈满,此时入栈,则上溢
top
top
top
top
top
1
2
3
4
5
0
A
B
C
D
E
F
top
top
top
top
top
top
栈空
top
base
base
假设maxsize=6
顺序栈的几种情况
7
初始化(栈置空)操作
判栈空函数
进栈操作
出栈函数
求栈深函数
读栈顶元函数
顺序栈上实现的操作
8

int inistack(sqstack s)
{=0;
return 1;}
9

void push(sqstack *s,elemtype x)
{if (s->top==maxsize) error(“栈满”);
s->top++;
s->elem[s->top-1]=x;
}
10