栈（stack）和队列（queue）是最常见的线性表数据结构之一，用途十分广泛。而且可以使用数组或者链表作为其存储容器

1.栈

栈是一种先进后出（First-In-Last-Out FILO）的数据结构。数据进入栈的操作称为“压栈（Push）”，而出栈的操作称为“出栈（Pop）”。

FILO线性表的特点是：存取元素的操作只在一段进行。即：先压栈的元素必定后出栈。

就好象常见的桶装饼干，最底层的饼干一定是最先装进去的，而我们先拿出来吃的饼干，则是最后装入的。

栈的最顶部称为栈顶，压栈和出栈都在这里进行。而底部由于没有什么大用途，所以也没有赋予特定的名称

如图，是一个栈的简单示意图

栈的应用包括函数的调用以及回文识别等等。

2.栈的实现

为了方便使用，在C++中，我们设计一个CStack类，通过这个类来操作堆栈。如你所见，这个类是模板类

关于模板函数和模板类，请参见模板函数和模板类
Read the rest of this entry »