文档介绍：第三章栈和队列
栈
桟的应用举例
栈与递归的实现
队列
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。
栈的修改是按照后进先出的原则进行的,栈又称为后进先出的线性表。
栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。
当栈中没有数据元素时,称为空栈。
栈的插入操作通常称为进栈,栈的删除操作通常
称为出栈。
a1
an-1
…
栈顶
栈底
进栈
出栈
栈的示意图
a0
设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。
(A) A,B,C,D (B) D,C,B,A
(C) A,C,D,B (D) D,A,B,C
已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。
(A) i (B) n-i
(C) n-i+1 (D) 不确定
栈的类型定义
ADT Stack {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
基本操作:
} ADT Stack
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
几个基本操作的实现
Status InitStack (SqStack &S)
{// 构造一个空栈S
=(ElemType*)malloc(STACK_INIT_SIZE*
sizeof(ElemType));
if (!) exit (OVERFLOW); //存储分配失败
= ;
= STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack &S)
{ /* 销毁栈S,S不再存在*/
free();
=NULL;
=NULL;
=0;
return OK;
}
Status ClearStack(SqStack S)
{ /* 把S置为空栈*/
=;
return OK;
}