一章栈和队列.pptVIP

第三章 栈和队列 本章内容 3.1 栈 3.1.1 栈的定义及基本运算 3.1.2 栈的存储结构和实现 3.1.3 栈的应用 3.2 队列 3.2.1 队列的定义及基本运算 3.2.2 队列的存储结构和实现 3.2.3 队列的应用 3.1.1 栈的定义及基本运算 栈(Stack)的定义 – 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(top),另一端为栈底(bottom)。当表中没有元素时称为空栈。 3.1.1 栈的定义及基本运算 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 3.1.1 栈的定义及基本运算 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 栈的定义及基本运算 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 栈的定义及基本运算 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 栈的定义及基本运算 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 栈的定义及基本运算 栈的基本运算 InitStack(S): 初始化栈S StackEmpty(): 判断栈是否为空 Push(e): 将元素e放入栈顶 Pop(e): 移走栈顶的元素，同时由e带回该元素的值 Gettop(): 获取栈顶的元素，但不从栈中移走 3.1.2 栈的存储结构和实现 3.1.2 栈的存储结构和实现 ? 顺序栈 – 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。 3.1.2 栈的存储结构和实现 顺序栈的类型定义 // -----栈的顺序存储表示----- # define STACK_INIT_SIZE 100; # define STACKINCREMENT 10; typedef struct { SElemType *base; //栈底指针，栈构造前和销毁后为空 SElemType *top; //栈顶指针，指向栈顶元素的下一位置 int stacksize; //当前分配的栈的存储空间数 }SqStack; 3.1.2 栈的存储结构和实现 ? 顺序栈 设S是SqStack类型的指针变量。base是栈底指针。Top是栈顶指针。 – 栈不存在条件S.base=NULL – 栈空条件S.top=S.base – 插入栈顶元素，栈顶指针S.top=S.top+1 – 删除栈顶元素，栈顶指针S.top=S.top-1 – 栈满条件S.top-S.base=S.stacksize 3.1.2 栈的存储结构和实现 顺序栈的C语言实现 (1) 初始化 Status InitStack(SqStack S){ //构造一个空栈 S.base = (ElemType *) malloc(STACK_INIT_SIZE *sizeof(SElemType)) ; if(!S.base) exit (OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE ; return OK; }//InitStack 3.1.2 栈的存储结构和实现 (2)判断栈空 int StackEmpty(SqStack *S) { return(S.base==S.top); } (3)判断栈满 int StackFull(SqStack *S) { return(S.top-S.base=S.stacksize); } 3.1.2 栈的存储结构和实现 (4) 元素入栈 Status Push(SqStack S, SElemType e){ //插入元素e为新的栈顶元素 if (S.top – S.base = S.stacksize) return OVERFLOW; //栈满 *S.top = e; S.top++; return OK; }//Push