03-数据结构-栈及队列1.doc

第三章 栈与队列 栈与队列：限定操作的线性表。 第一节 栈 一、逻辑结构 1、栈的定义 限定只能在表的一端进行插入、删除的线性表。 　　栈顶top，栈底bottom。 　　后进先出LIFO表(Last In First Out) 实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题”…… 2、基本操作 进栈Push/出栈Pop 取栈顶元素GetTop 判别栈空StackEmpty/栈满StackFull 3、栈的应用背景 许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=》问题分解的步骤和求解的步骤次序恰好相反。 二、顺序存储结构 动态顺序存储结构：存储空间随栈的大小而变化。 #define STACK_INIT_SIZE 100 //初始化时分配的空间 typedef struct //定义栈类型 { ElemType *base,*top; //栈底、栈顶指针 int stacksize; //栈的存储空间大小 }SqStack; SqStack S; //定义一个栈结构 1、初始化栈 Status SqStack_Init(SqStack S) { S.base=malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) return(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK); } 栈空： S.top==S.base 栈满： S.top==S.base+S.stacksize 2、进栈 Status SqStack_Push(SqStack S,ElemType e) { if(S.top==S.base+S.stacksize) return(OVERFLOW); S.top=e; S.top++; return(OK); } 3、出栈算法 Status SqStack_Pop(SqStack S,ElemType e) { if(S.top==S.base) return(UNDERFLOW); S.top--; e=S.top; return(OK); } 缺点：空间浪费 思考：二栈合用同一顺序空间？ #define maxsize=100 int stack[maxsize], top0=0, top1=maxsize-1; int push0(int e) { if(top0 top1) return(0); stack[top0]=e; top0++; return(1); } int push1(int e) { if(top0 top1) return(0); stack[top1]=e; top1--; return(1); } int pop0(int *e) { if(top0==0) return(0); top0--; *e=stack[top0]; return(1); } int pop1(int *e) { if(top0==0) return(0); top0++; *e=stack[top1]; return(1); } 三、链栈 typedef struct linknode // 栈中结点类型 { ElemType data; struct linknode *link; }LinkNode; typedef struct // 定义栈类型 { LinkNode *top; // 栈顶指针 int stacksize; // 栈的大小(可选) }LinkStack; LinkStack S; 初始化: S.top==NULL; S.stacksize==0 栈 空：S.top==NULL 栈 满：系统内存不够 1、进栈 Status LinkStack_Push(LinkStack S，ElemType e) { LinkNode *p; p=(LinkNode *)malloc(sizeof(LinkNode)); if(p==NULL) return(OVERFLOW); //上溢 p-data=e; p-link=S.top; S.top=p; return(OK); } 2、出栈 Status LinkStack_Pop(LinkStack S,ElemType e) { LinkNode *p; if(