数据结构第三章.pdf

第三章 栈和队列 3.1 栈 1.栈的概念及运算： 栈(stack)：栈是运算受限的线性表，只限制在表的一端进行运算，称 为栈顶(top),另一端称栈底(bottom)，当表中无元素时称为空栈。 栈又称为后进先出（last in first out）的线性表。 栈又称为先进后出（first in last out）的线性表。 例 如：a1,a2……an ==>an,an-1,……a1 一叠书，一叠重物 运 算： 置空栈SETNULL(S) 判空栈EMPTY(S) 进栈PUSH(S,X) 退栈POP(S) 取栈顶TOP(S) //不改变栈的状态 2.顺序栈 顺 序 栈：栈的顺序存储结构称为顺序栈。 栈底位置不变，栈顶指针top用来指示栈顶位置 定 义：typedef struct { datatype data[maxsize]; int top; } seqstack; seqstack *s; 上溢，下溢，设初始情况下s->top=-1; 运 算：图示 置空栈 void SETNULL(seqstack *s) { s->top=-1; } 判栈空 int EMPTY(seqstac