文档介绍：栈
队列
递归
第三章栈和队列
栈( Stack )
定义:是限定仅在表尾进行插入或删除操作的线性表。
允许插入和删除的一端
称为栈顶(top),另一端
称为栈底(bottom)
特点:后进先出(LIFO)
a1
top
bottom
an
.
.
.
.
进栈
出栈
栈的主要操作
ADT Stack {
//对象由数据类型为StackData的元素构成
int Push (stack *S, StackData x); //进栈
int Pop (stack *S, StackData &x); //出栈
int GetTop (stack *S, StackData &x); //取栈顶
void InitStack (stack *S); //置空栈
int StackEmpty (stack *S); //判栈空否
int StackFull (stack *S); //判栈满否
}
栈的表示和实现
顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指向栈顶元素在顺序栈中的下一个位置,
base为栈底指针,指向栈底的位置。
base
空栈
a 进栈
b 进栈
a
a
b
top
base
top
base
top
top
top
a
b
c
d
e
e 进栈
a
b
c
d
e
f 进栈溢出
a
b
d
e 出栈
c
base
base
base
top
顺序栈的类型表示:
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef char StackData;
typedef struct { //顺序栈定义
StackData *base; //栈底指针
StackData *top; //栈顶指针
int stacksize;//当前已分配的存储空间
} SeqStack;
判栈空
int StackEmpty (SeqStack *S) {
if( S->top == S->base ) return 1 //判栈空,空则返回1
else return 0; //否则返回0
}
判栈满
int StackFull (SeqStack *S) {
if( S->top- S->base >= S-> StackSize ) return 1
//判栈满,满则返回1
else return 0; //否则返回0
}
顺序栈的基本运算:
初始化
void InitStack ( SeqStack *S) { //置空栈
S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW);
S->top = S->base ;
S->stacksize= STACK_INIT_SIZE ;
Return ok;
}
入栈
int Push (SeqStack *S, StackData x) {
//插入元素x为新的栈顶元素
if ( StackFull (S) ){
S->base =( StackData *)malloc(S->base ,
(S->stacksize+ STACKINCREMENT) * sizeof(StackData));
if(! S->base)exit(overflow);
S->top= S->base + S->stacksize;
S->stacksize+= STACKINCREMENT; //追加存储空间
}
*(S->top)=x;
(S->top)++;
Return ok
}
取栈顶元素
int Gettop (SeqStack *S, StackData &x) {
//若栈空返回0, 否则栈顶元素读到x并返回1
if ( StackEmpty(S) ) return 0; (S->top)--;
x = *(S->top);
return 1;
}