栈的操作与应用.docVIP

栈的操作与应用 在工作中，我们常常会遇到诸如函数的返回地址的保存、判断一个表达式中的括号是否匹配、迷宫求解、表达式求值、递归等问题。在函数的调用过程中，需要保存返回地址和参数；在高级语言的编译过程中，需要判断一个表达式是否符合语法要求，如果表达式中包含括号，要判断括号是否正确匹配；在求解迷宫的问题中，需要记住已走过的路径。这类问题的共同特点是，既需要保存数据元素的值，也需要保存数据元素插入的顺序，并且要按照后进先出的原则插入或删除数据元素，这类问题我们可以通过栈实现。 预备知识 3.1.1 栈的定义）.1.2 栈的图 31顺序栈示意图 const int StackSize=10 //栈的空间长度 template class T //定义模板类SeqStack class SeqStack { … private: T data[StackSize]; //存放栈元素的数组 int top; //栈顶指针，指示栈顶元素在数组中的下标 }; 入栈算法的描述 （1）判断栈空间是否已满，或已满，抛出“上溢”异常 （2）将元素压入栈项 template class T void SeqStackT::Push(T x) //元素x进栈 { if (top== StackSize-1) throw 上溢; //如果栈满，抛出异常 top++; data[top]=x; } 出栈算法的描述 （1）判断栈是否已空，或已空，抛出“下溢”异常 （2）将栈顶元素弹出 template class T T SeqStackT::Pop( ) //栈顶元素出栈 { T x; if (top==-1) throw 下溢; //如果栈已空，抛出异常 x=data[top--]; return x; } 顺序栈的操作情况见图3-2 （a）栈空 （b）栈满 （c）栈中有3个元素 图 32顺序栈的操作示意图 高级语言的数组下标从0开始，当top＝StackSize-1时，栈已满，元素不能进栈，当top＝-1时，栈空，元素不能出栈。 采用顺序结构存储栈时，要预先估计栈空间的长度，避免由于栈的空间不足，使元素不能进栈，也不能预留空间过多，造成存储空间的浪费。 算法的时间性能分析： 由于入栈和出栈都在栈顶进行，操作简单，时间复杂度均为O(1)。 3.1.2.2 栈的链式存储结构 线性表可以采用链式存储结构，也可以用链式结构表示栈，称为链栈，在链栈中，每个结点由两个域组成，一个域为数据域，用来表示栈中数据元素的值，另一个域为指针域，用来指出栈中的下一个元素的地址。由于入栈和出栈操作只在栈的一端进行，因此要选择链栈的一端做栈顶，考虑链式结构的特点，要找到表尾的位置，必须从表头开始，如果用表尾做栈顶，在入栈和出栈操作时，均要从表头开始遍历到表的尾部，速度慢；因此选择表头做栈顶，表尾做栈底。由于栈的操作只在栈顶进行，不存在在栈的中间或栈底插入元素或删除元素的情况，所以链式栈可以没有头结点，假设依次向栈中压入元素a0,a1,a2,a3后，链式栈的存储结构见图3-3。 图 33链栈存储结构示意图 struct Node { T data; NodeT *next; }; class LinkStack { … private: NodeT *top; //栈顶指针即链栈的头指针 }; 元素入栈算法的描述 （1）申请空结点，将预入栈元素存入结点的数据域 （2）将结点压入栈项 template class T void LinkStack::Push(T x)//向栈中插入一个元素x { s=new NodeT; s-data=x; //申请一个数据域为x的结点s s-next=top; top=s; //将结点s插在栈顶 } 元素出栈算法的描述 （1）判断栈是否已空，若栈已空，抛出“下溢”异常 （2）若栈不空，栈顶元素出栈 template class T T LinkStack::Pop( )//删除栈顶元素 { if (top==NULL) throw 下溢; x=top-data; //暂存栈顶元素 p=top; top=top-next; //将栈顶结点摘链 delete p; return x; } 链栈的操作情况见图3-4。 （a）栈空 （b）a3入栈前 （b）a3入栈后 图 34链栈的操作示意图 算法的时间性能分析 链栈的入