数据结构第3章栈和队列.ppt

文档介绍：第3章栈和队列




---表达式求值
第3章栈和队列




第三章栈和队列

:
栈(Stack) 是限定仅在表的一端进行插入或删除操作的线性表。
P44
P45
栈的存储结构
有两种存储结构:
顺序栈(常用);
链栈
1、顺序栈
顺序栈的类型定义:
//-- -- --栈的顺序存储表示-- -- --#define STACK_NINT_SIZE 100;//存储空间初始分配量#define STACKINCREMENT 10; //存储空间分配增量typedef struct{    SElemType *base; //在栈构造之前和销毁之后,base的值为NULL    SElemType *top; //栈顶指针    int stacksize; //当前已分配的存储空间,以元素为单位}SqStack
顺序栈的结构举例
//-- -- --基本操作的函数原型说明-- -- --Status InitStack(SqStack &S);    //构造一个空栈SStatus GetTop(SqStack S,SElemType &e);    //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERRORStatus Push(SqStack &S,SElemType e);    //插入元素e为新的栈顶元素Status Pop(SqStack &S,SElemType &e);    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
2、链栈
链栈的类型定义:
typedef struct LNode{//结点类型    ElemType data;    struct LNode *next;}Lnode,*Linkstack;Linkstack S;