文档介绍：数据结构 第三章栈和队列
*
第三章栈和队列
栈
栈和队列也是线性表,只不过是操作受限的线性表。
栈是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶,表头端称栈底。如图。
an
...
a2
a1
栈底
栈顶
出栈
进栈
栈顶(TOP)--允许插入和删除的一端。
栈底(bottom)--不允许插入和删除的一端。
空栈--表中没有元素。
进栈---最先插入的元素放在栈的底部。
退栈---最后插入的元素最先退栈。
所以栈又称为后进先出的线性表(LIFO表,Last In First Out)
栈
栈的类型定义
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 端为栈底。
基本操作:
InitStack(&S) 操作结果:构造一个空栈S。
DestroyStack(&S) 初始条件:栈S已存在。 操作结果:栈S被销毁。
ClearStack(&S) 初始条件:栈S已存在。 操作结果:将S清为空栈。
StackEmpty(S) 初始条件:栈S已存在。 操作结果:若栈S为空栈,则返回TRUE,否则FALSE。
栈
栈的类型定义
StackLength(S) 初始条件:栈S已存在。 操作结果:返回S的元素个数,即栈的长度。
GetTop(S, &e) 初始条件:栈S已存在且非空。 操作结果:用e返回S的栈顶元素。
Push(&S, e) 初始条件:栈S已存在。 操作结果:插入元素e为新的栈顶元素。
Pop(&S, &e) 初始条件:栈S已存在且非空。 操作结果:删除S的栈顶元素,并用e返回其值。 } ADT Stack
栈
栈的表示和实现----顺序表示
#define STACK_INIT_SIZE 100 //栈内存的初始分配量,以sizeof(ElemType)为单位   
 #define STACKINCREMENT 10 //栈内存的分配增量,以sizeof(ElemType)为单位    
typedef struct {    
SElemType *base; //存储空间的基址,数据元素的数据类型约定为SElemType    
 SElemType * top; //表示栈顶,如果top==base,表示空栈    
int stacksize; //当前分配的存储容量,以sizeof(ElemType) 为单位 } SqStack
3 2 1 0
Top=base 空栈
Top
base
A
3 2 1 0
TOP
A进栈
base
3 2 1 0
D
C
B
A
B、C、D依次进栈
TOP
base
3 2 1 0
B
A
TOP
D、C依次退栈
base
3 2 1 0
B、A退栈
base
TOP
栈
栈的表示和实现----顺序表示
顺序栈基本操作的实现
Status InitStack(SqStack &S) {     //为栈S分配存储空间,并置S为空栈   
 =(SElemType *)malloc(STACK_INIT_SIZE* sizeof( SElemType));
if(!) exit(OVERFLOW);
=; //置栈S为空栈  
=STACK_INIT_SIZE;    
 return OK;  }//InitStack
栈的表示和实现----顺序表示
顺序栈基本操作的实现
Status GetTop(SqStack S,SElemType &e) {     //若栈不空,则用e返回S的栈顶元素并返回OK,否则返回ERROR     
if(==) return ERROR;
e=*(-1);    
  return OK; }    //GetTop
栈的表示和实现----顺序表示
顺序栈基本操作的实现
Status Push(SqStack &S, SElemType e) //将e插入栈S中并使之成为栈顶元素 
if(->=)  { //栈满,追加存储空间    
=(SElemType *) realloc( , (+STACKINCREME