在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。

根据参考文献[5]-[8]的介绍，如果选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

通过本问题的探究与设计，培养了学生对算法分析的能力，同时加强锻炼了学生以计算机编程解决数学复杂问题，达到了跨学科知识的联系与运用，以及理论与实际的相结合。另外，对栈的理解与运用有了更深的理解与掌握，同时对比分析相同问题采用不同方法解决的优缺性，对学生今后学习与实践有很大的帮助。

1。2  C++语言

C语言[9]-[11]是一门通用计算机编程语言，应用广泛C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

C++是在C语言的基础上开发的一种面向对象编程语言，应用广泛；C++支持多种编程范式 。面向对象编程、泛型编程和过程化编程其编程领域众广，常用于系统开发，引擎开发等应用领域，是至今为止最受广大程序员受用的最强大编程语言之一。

2。 栈的应用研究

2。1  栈的非递归算法

定义1[11]：栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 

　　栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。栈可以用来在函数调用的时候存储断点。其结构实例如下：

     图1栈的结构示意图

对于一个栈中元素的操作来说，其成员函数主要有以下三个函数：

Push()函数（进栈）：

template<class T> 

void LinkedStack<T>::Push(const T& x)

{ //将元素值x插入到链式栈的栈顶，即链头 

      LinkNode<T> *newNode=new LinkNode<T>(x);

      newNode->link=top; top=newNode;

      assert(top!=NULL);//创建新结点失败退出 

}

Pop()函数（删除栈顶结点）：

template <class T> 

bool LinkedStack<T>::Pop(T& x)

{ //删除栈顶结点，返回被删栈顶元素的值

  if(IsEmpty()==true) return false; //若栈空则不退栈，返回 

     LinkNode<T> *p=top; //否则暂存栈顶元素 

     top=top->link; //栈顶指针退到新的栈顶位置 

     x=p->data;delete p; //释放结点，返回退出元素的值 

     return true; 

}

getTop()函数（取出栈顶结点）：

template<class T> 

bool LinkedStack<T>::getTop(T& x)const