10.组装火车的乐趣。国庆假期结束了。我真的不想来上班。国庆节前继续。上一篇文章是关于使用数组实现的使用栈结构的两个致命弱点是使用前必须指定大小，效率很差。于是之前的大牛们开始思考如何提高效率？在C/C++语言中，有一种东西可以直接操作内存，叫做指针，可以动态指定大小，于是人们不得不思考如何利用指针来克服原有的弱点，重新实现数据结构。在使用指针实现之前，我们先看看为什么数组可以实现栈等类似结构。首先，一个数组可以通过下标来遍历，也就是说我们可以从一个元素开始搜索到下一个元素或者某个元素。其次，数组可以包含元素。那么我们就需要用指针来构造一个具有这两个特性的结构体，也就是说这个结构体必须包含一个元素并且至少可以让我们访问到下一个元素，也就是可以作为一个整体来实践。在这种思路下，我们可以肯定，一个结构体包含元素是很简单的，只要为它声明一个成员变量，然后如何使用某种方法让它识别自己或访问它作为整个？下一个元素呢？我们可以使用指针，所以在创建栈之前，我们首先要做的就是创建这样一个结构。通常，这种结构被称为节点（Node），意思是“一个存在于运行时的物理元素，它代表一种可计算的资源，它通常至少具有一些内存和处理能力”。从这个定义中，也可以看出节点的特点。structNode{charele;Node*next;};其实你可以把Node想象成一节火车车厢，里面的元素就是火车里面的载荷，指针就是车厢连接处的钩子，通过钩子连接起来组成一列火车。事实上，这个小小的结构体包含了很多计算机知识。你可以问问自己为什么这个Node*不能写成Node？好了，有了这辆车，那我们就要用这辆车组成火车。使用Node的好处之一是可以自由组装。虽然这个好处在栈结构中是看不出来的，但是在后面的结构中是有的。它会变得越来越明显。想象一下，车站里停着这样一列火车，火车前面有一个站台，也就是说火车前面是没有路的，这里有一个细节。对于这个车头，你可以把它看成是一辆普通的车厢，或者把它看成是一辆特殊的车厢，把它看成一辆不能载客的车厢。它的作用是表示后面有火车，没有元素。在实现上，这样的节点称为头节点。为了简单起见，我们使用第一种方法。当然，这个问题我会在后面再描述。回到火车的问题，我们要组装火车。火车前面没有铁轨，只能从火车尾部把火车一节一节地组装起来。拼装的方法是将连接在火车车厢上的挂钩一个一个地连接起来，这样就可以组成一列火车。拆卸车厢时，车厢只能从后面一个接一个地拆卸，为堆叠式结构。我们先看一下头文件的组成。classStack{public:Stack();~Stack();voidPush(charele);charPop();intTop();charGetValue(intPos);boolCheckEmpty();intGetCount();private:Node*cur;intcount;};一部分类似于使用数组的实现，不同的是构造函数中没有size，因为可以使用指针动态设置size，另一个是成员变量换成节点，就像一辆马车。接下来，我们需要考虑如何实现它。构造函数是初始化。建造上面提到的火车，如果一开始什么都没有，就应该先把机车打开收起来，然后在机车后面再接上任何东西。程序中就是指针指向null，可以理解为机车后面的钩子上没有挂任何东西。然后是推动。如果现在要在后面挂一辆车，需要打开车（声明一个新的节点），用下一辆车的钩子挂前面的车（在程序中，就是把当前的）Node结构体的指针指向“->”这个新添加的节点，符号“->”我认为是C/C++中最形象的符号，因为看到它就有指向的意思），需要标记第一辆下一辆车的位置，因为否则你将不知道下一辆新车在哪里。接下来是Pop，你可以想象卸车，因为你首先要让车里的乘客下车，所以你得先找个地方让乘客下车再卸车（声明一个变量保存Node中的元素），然后重新找到卸载后的最后一个节点，去掉钩子（消除这个节点的内存）。***一个是析构器，你可以理解为如果我不想要我组装的整列火车怎么办（当然这个比喻不太恰当），你需要把所有的车厢一一卸下来，让它们不要'占用rails资源。使用Node实现的栈如下：Stack::Stack(){cur=newNode();count=0;}Stack::~Stack(){Node*tmp=newNode();while(cur->next!=NULL){tmp=cur;cur=tmp->next;deletetmp;}deletetmp;delete[]stackArray;}boolStack::CheckEmpty(){return(count==0);}voidStack::Push(charele){节点*tmp=newNode();tmp->ele=ele;tmp->next=NULL;if(count==0)cur->ele=ele;else{tmp->next=cur;cur=tmp;}计数++；}charStack::Pop(){if(count==0){cout<<"stackisempty!"<
