《大学计算机基础与思维》第2.3栈与队列.PPTVIP

3.4 堆栈 3.4 堆栈及其应用——定义 插入、删除只在线性表一端进行的线性表被称为栈。 后进先出----LIFO (Last In First Out) 栈顶浮动 栈底固定 顺序存储结构： 顺序栈 链式存储结构： 链栈 3.4.1. 顺序栈 #define MAXSIZE 100 //栈容量 typedef struct { DataType data[MAXSIZE ]; //存储空间 int top; //栈顶指针 }SStack; 栈空时，top=-1；非空时，top位于栈顶元素的位置 顺序栈的空间固定 SStack *InitStack( ) { //构造一个空栈s SStack * S ； S =(SStack *)malloc(sizeof(SStack)); S-top=-1; return S; } int EmptySStack(SStack *S) { //若栈空，则返回1，否则返回0 if (S-top==-1) return 1; else return 0; } int GetTop(SStack *S, DataType *x) { //若栈不空，则返回1，否则返回0 if (S-top==-1) return 0; else { x= (DataType *)malloc(sizeof(DataType)); *x= S-data[ S-top]; return 1; } } int Push(SStack *S, DataType x) { //插入元素x为新的栈顶元素 if (S-top==MAXSIZE-1) return 0; else {S-top++; S-data[ S-top]=x; return 1; } } int Pop(SStack *S, DataType *x) { //若栈不空，则删除S的栈顶元素，用x返回其值，并返回1；否则返回0 if (S-top==-1) return 0; else { x= (DataType *)malloc(sizeof(DataType)); *x= S-data[ S-top]; S-top--; return 1; } } 3.4.2. 链栈 typedef struct lnode{ DataType data; //存储栈元素 struct lnode *next; //指针 }LSStack; LSStack *top; 栈空时，top=NULL；非空时，top指向栈顶元素 链栈的空间不固定 LSStack *InitStack( ) { //构造一个空链栈 return NULL; } int EmptySStack(LSStack *top) { //若链栈空，则返回1，否则返回0 if ( top==NULL) return 1; else return 0; } int GetTop(LSStack * top, DataType *x) { //若链栈不空，则返回1，否则返回0 if (top==NULL) return 0; else {x= (DataType *)malloc(sizeof(DataType)); *x= top-data; return 1; } } void Push(LSStack * top, DataType x) { //插入元素x为新的链栈顶元素 LSStack * p; p= (LSStack *)malloc(sizeof(LSStack)); p-data=x; p-next=top; top=p; } int Pop(LSStack * top, DataType *x) { //若链栈不空,则删除链栈的栈顶元素，用x返回其值，并返回1；否则返回0 if (top==NULL) return 0; else { x= (DataType *)