中缀表达式转后缀表达式并求值C++数据结构链栈应用

中缀表达式转后缀表达式并求值C++数据结构链栈应用

根据栈的先进后出的特点，很容易设置栈结构的接口：入栈、出栈、判空、size()等，熟悉数据库的同学都知道数据库无非就是四种操作：增、删、改、查，其实对于一个数据结构的接口而言，也是这四种操作，就栈而言，入栈即增操作、出栈即删操作、由于栈是线性表结构，所以查和改操作都需要遍历整个栈结构。现在已经知道了栈的接口操作，我们就可以用实现表的方法来实现一个栈结构，其实也就两种，用链表或数组实现栈。
但是，在C++标准库中已经为我们实现了栈结构，而且是按照最高效率、最优的标准实现的，你可以放心的使用C++标准库提供的栈结构，以C++一贯的作风，其实现的栈结构是一个栈类型，定义在头文件中，使用的时候只需要#include该头文件就行。
根据C++STL的解释，或C++Primer（第五版P329）的解释，都把stack类型称为一个容器适配器（配接器），并没有称其为一个容器，尽管如此，你可以把stack看作是一个特殊的容器，所谓适配器（配接器），指的是一种机制，一个容器适配器使一个容器的行为看起来像另外一个容器，这句话说的是什么意思呢？这是因为C++的容器适配器都是基于基本容器实现的，比如stack就是与queue实现的（默认，也可以显示指定为vector），这也导致了任何stack的操作接口都是直接调用底层容器的操作来完成的，如stack的push操作（入栈）就是调用queue的push_back操作来完成的。下面给出STL中stack的定义文