文档介绍：第三章栈和队列
栈
队列
栈与递归的实现
1 栈的定义
栈(Stack)是限制在表的一端进行插入和删除运算的线性表。
a1
a2
a n-1
a n
……
top
base
出栈
进栈
通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Base)。
当表中没有元素时称为空栈。
栈称为后进先出表(LIFO)
(1)初始化
2、栈的基本操作
(2)进栈
(3)退栈
(4)取栈顶元素
(5)判栈是否非空
(6)置栈空
3、栈的抽象数据类型的定义
P45
ADT Stack {
.
.
.
}
栈有两种存储表示方法。顺序栈、链栈。
栈的表示和实现
顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。同时附设指针top指示栈顶元素在顺序表中的位置。
通常的****惯做法是以top=0表示空栈。
C语言中数组的下标约定从0开始,则当以C语言作描述语言时,如此设定会带来很大不方便;
一个合理的做法是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时再逐段扩大。
另一方面,由于栈在使用过程中所需要最大空间的大小很难估计,因此,一般来说,在初始化设计空栈时不应限定栈的最大容量。
设定两个常量:STACK_INIT_SIZE------存储空间初始分配量
STACKINCREMENT------存储空间分配增量
typedef Struct
{
SElemType *base;
SElemType *top;
int stacksize; //栈的当前可使用的最大容量
} SqStack;
1、顺序栈
栈的初始化操作为: 按设定的初始分配量进行第一次存储分配,base称为栈底指针,在顺序标中,它始终指向栈底的位置,若 base的值为NULL,则表明栈结构不存在.
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
top
base
1、顺序栈
称top为栈顶指针,其初始值指向栈顶;base为栈底指针;始终指向栈底;
top==base可作为栈空的标记
每当插入新的栈顶元素时,指针top增1;
删除栈顶元素时,指针top减1
非空栈中的栈顶指针始终在栈顶元素的下一位置上。
栈的顺序存储表示
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef Struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
P46
栈的基本操作
栈的链式存储结构称为链栈,它是运算受限的单链表,插入和删除操作仅限制在表头位置上进行。
由于只能在链栈头部进行操作,故没有必要像单链表那样附加头结点------栈顶指针就是链栈的头指针。
2、链栈
链栈的类型说明如下:
typedef struct stackNode {
SElemtype data;
struct stackNode *next;
} stackNode, *LinkStack;
计算顺序
输出顺序
例1: 数制转换:十进制数N和其他d进制数的转换是计算机实现计算的基本问题。其中一个简单算法基于下列原理:
栈的应用举例
例如:(1348)10 = (2504)8 ,其运算过程如下:
N=(N div d)d+N mod d
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2