文档介绍：[内容提要]
第三章栈和队列
1
定义:栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表,简称LIFO线性表。
允许进行插入和删除的一端称为栈顶(top)
不允许插入和删除的一端称为栈底(bottom)
不含元素的空表称为空栈。
特点:后进先出(LIFO)或先进后出(FILO)
栈的基本概念
2
栈的示例图
a1
a2
a3
an
栈顶(top)
栈底(bottom)
进栈
出栈
1
2
3
4
5
进
出
3
栈的基本操作
INISTACK(S):初始化操作。设置一个空栈S。
EMPTY(S):判栈空函数。若S为空栈,函数值为1,否则为0。
SIZE(S):求栈深函数。函数值为栈中当前的元素个数。
TOP(S):读栈顶元函数。若栈S不空,函数值为栈顶元素,否则为空元素NULL。
PUSH(S,x):进栈操作。将元素x插入栈S中,使x成为栈S的栈顶元素。
POP(S):出栈函数。若栈S不空,函数值为栈顶元素,且从栈中删除当前栈顶元素,否则函数值为空元素NULL。
CLEAR(S):栈置空操作。不论栈S是否为空栈,将S置为空栈。
4
用除法把十进制数转换成二进制数,把所有的余数按出现的逆序排列起来(先出现的余数排在后面,后出现的余数排在前面),十进制数35转换成二进制数
35
17
8
4
2
1
0
1
1
0
0
1
余数
结果:10011
例:
5
栈的顺序存储结构(顺序栈)
顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素,通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置或后一空位置(下标)。
顺序栈的类型说明:
#define maxsize <栈可能的最大数据元素数目>
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
栈的链式存储结构
定义:栈的链式存储结构,简称链栈,它的组织形式与单链表类似,链表的尾部结点是栈底,链表的头部结点是栈顶。
9
栈的链式存储结构
F
top
data
next
E
D
A
NULL
栈顶
栈底
链栈的类型定义:
       typedef struct stacknode
{elemtype data             struct stacknode *next   }stacknode;
typedef struct
{ stacknode *top;  //栈顶指针  }linkstack;
10