第三章栈和队列栈和队列是一种操作受限的线性表3.1栈(stack)只能在表尾进行插入和删除表尾称栈顶(top)表头称栈底(bottom)栈按后进先出的原则进行（LastIn FirstOut)
1 第三章 栈和队列 栈和队列是一种操作受限的线性表 3.1 栈(stack) 只能在表尾进行插入和删除 表尾称栈顶( top) 表头称栈底(bottom) 栈按后进先出的原则进行（Last In First Out)
栈的抽象数据类型的定义ADT Stack{数据对象：D={a;|a,EElemset,i=l,2,,n，n>=0}数据关系：R1=[<ai-1,a,>l ai-1,a;ED,i=2,3,",n约定a.端为栈顶，a,端为栈底。基本操作：initStack(&s)destroyStack(&s)clearStack(&s)Stackempty(s)Stacklength(s)GetTop(s,&e)Push(&s,e)Pop(&s,&e)ATD Stack2
2 ADT Stack { 数据对象：D={ ai | ai∈Elemset,i=1,2,.,n, n>=0 } 数据关系：R1={< ai-1 , ai >| ai-1 ,ai ∈D,i=2,3,.,n } 约定an端为栈顶，a1端为栈底 。 基本操作： initStack(&s) destroyStack(&s) clearStack(&s) Stackempty(s) Stacklength(s) GetTop(s,&e) Push(&s,e) Pop(&s,&e) } ATD Stack 栈的抽象数据类型的定义
栈的表示和实现1）顺序栈：用一组地址连续的存储单元依次存储自栈底到栈顶的各元素typedef struct{ SElemType *base;SElemType *top;intstacksize;} SqStack;指向栈底的位置；若为NULL，则表示栈不存在。base:top:指向栈顶元素的下一位置。初值指向栈底，即top=base3
3 1）顺序栈：用一组地址连续的存储单元依次存储自栈底到 栈顶的各元素 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; base：指向栈底的位置；若为NULL，则表示栈不存在。 top： 指向栈顶元素的下一位置。 初值指向栈底，即top=base 栈的表示和实现
栈的初始化Status InitStack(SqStack&S){S.base=(SElemType*)malloc(STACK INIT_SIZE*sizeof(SElemType))if (!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE ;return OK;1
4 栈的初始化 Status InitStack(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType)) if (!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE ; return OK; }
读取栈顶元素的值Status GetTop(SqStack S, SElemType &e)IIS为空栈？( if(S.top= =S.base)return ERROR;e=*(S.top-1)return OK;1
5 读取栈顶元素的值 Status GetTop(SqStack s, SElemType &e) { if(S.top= =S.base) //S为空栈？ return ERROR; e=*(S.top-1) return OK; }