你所能用到的数据结构（六）

八、数据结构不一定很枯燥

  正如我现在实习的公司的一个同事说的那样，数据结构是一本催眠的书，我想对于大多数人应该是这样的，当然对我也是，看着一大堆的算法，结构模型，不想睡觉那应该可以归结为geek一类的，但是呢，后来我找到了一个办法，就是动手，我发现无论看的时候有多无聊，写写程序所带来的那种兴奋感和成就感现在已经成为了支撑看完我一本书的精神动力，所以我想在我开始从堆栈到图的过程中，我尽我所能让所写的程序有更大的互动性，由于我的目的是能够让一些初学者对于编程写代码更感兴趣，而且我这水平也只能给初学者提供一点我以前学习的经验了，我本来想用MFC，用图形化界面来增加交互性的，后来我发现对于一个没有学过MFC的人，如果想很简短的说清楚还是很难的，所以我只能尽我所能在DOS的黑屏下开发出一些交互性来了。我始终相信最简单的东西才是最根本的，DOS界面虽然简陋，没有界面，更不可能有WPF这些技术做出来的更炫更好的界面，但是往往就是这种简陋的界面才能更容易让人去重视本质和核心的东西。虽然说我是想能够提供更多的交互性，但是毕竟本人水平有限，加上思维僵化，所以我尽我最大的努力好了。

九、你不能小看任何简单的东西

堆栈，稍微对数据结构有点了解的人，都会觉得这个结构太简单了，其模型就是先进后出，可以想象成为一摞盘子，盘子一个叠一个的，在正常情况下，你会永远往上摞盘子并且从上面取盘子，这样抽象出来的一个结构大体可以称之为堆栈。如果你玩过三国杀，你被乐不思蜀了，这时候闪电轮到了你的头上，先判断乐不思蜀还是闪电？根据规则是后来的先判，于是翻牌判断闪电，然后乐不思蜀。这也就是一个堆栈啊！这个结构广泛的应用于我们生活中，同时也广泛的应用于计算机中，电脑程序之所以能够运行，如果没有堆栈这个结构是不行的，你写的函数能够正确的被调用，没有堆栈的帮助也是不可以的。所以说，看起来不起眼的结构往往最实用，虽然结合堆栈的算法相比使用图进行的算法要简单的多，但是就实际运用来说，人们总是会选那些简单，实用，高效的东西。对堆栈的学习不仅仅是对数据结构整个的一个启蒙而且更是了解数据结构到底在实际中有多大应用的一个起点，大学学的几门基础课，我觉得如果你想成为一个工程师，那么你用到最多的三门课应该是数据结构，计算机网络和操作系统。

      那么，如何实现这样一个先进后出的结构呢？首先，堆栈肯定是一种集合，一种具有特殊性质的集合，那么很自然的想到利用数组来实现，比方说我们有一个20个长度的数组a，我们将第一个数放在索引为0的位置上，现在第二个数，我们将第一个数向后挪一位，挪到a[1],然后将新数放到a[0],依次类推，这样取数的时候永远取a[0]的数，然后将后面的数前移，这样就能达到一个先进去的数最后才能取到的目的。但是这种实现方案的最大的缺点是你每次都要移动数组，这对计算机所造成的开销是非常大的，特别是对数组这样一个效率很低的结构（别小看数组，数组也是一种数据结构）。那么，我们可不可以有所改进呢？可以很自然的想到如果我将每次新进来的元素都放在数组的末尾，也就是每次都在数组的最末尾添加元素，那样对于插入操作的效率是最快的，那就将到来的数依次从0插入，如果需要取数的话，那么永远从最后一个数开始取，同时用一个变量标示数组中实际有多少元素，无疑，这样对于效率的提高是非常大的。还有没有更大的效率的实现方式呢？当然，使用指针，永远记住，指针是一个很好的工具，如果你所做的是大型的系统，那么良好的使用指针所带来的效率的提高是会让你感到惊奇的一件事。对于使用指针实现的堆栈，我准备下一节再写。

      好，基本思路确定了，那么我们就开始写了（这里我默认你已经懂得C++基本知识，不然你也不会看数据结构了），但是我们还发现一个问题，如果使用数组，那么我怎么知道我要用的堆栈有多大？这个解决的办法很多，第一个就是申明一个很大的数作为这个数组的大小，但是很大是多大？永远有比很大更大的数，更不用说这样做导致的内存浪费，可能在你平时编写小程序的时候，你无法体会到内存浪费对于一个程序员深深地痛，另外一个痛是内存泄露，所以有些东西还是先培养出一种习惯比较好的。第二个就是使用指针动态申请数组的大小，这样的话，我们需要一个含有参数的构造函数（如果你不知道什么叫构造函数的话，那么。。。那么。。。那么你可以关了这个界面，不过我的打算是把数据结构写完了，写介绍基础C++的文章，那个时候你可以再来看看），这个参数你要申明的数组的大小。

     对于堆栈这个类的成员函数（突然觉得专业名词好多？其实你可以去学学C++），添加元素的专业叫法是push（压），取出元素的专业叫法是pop(弹出),你可以想象那种前几年流行过的一种存硬币的圆柱状物品，你可以把硬币一个一个压入那里面，然后弹出最上面的硬币。除了这两个，还可以有的是检查堆栈是否为空，返回栈顶元素（不弹出）和返回堆栈大小，为了增加交互性和尽量简单，我的实现里加入了一个遍历堆栈元素的成员函数（这个是不好的，违背了堆栈的原理）。那么好，先看看.h文件。

 1 #ifndef STACK_H
 2 #define STACK_H
 3 class Stack{
 4 public :
 5     Stack(int size);
 6     ~Stack();
 7 
 8     void Push(int ele);
 9     int Pop();
10     int Top();
11     int GetValue(int Pos);
12     bool CheckEmpty();
13     int GetCount();
14 
15 private:
16     int *stackArray;
17      
18     int count;
19 };
20 #endif

      .h文件我的理解对于初学者可以将它看做一个索引，它让你看看一个类里大概有什么东西。看完索引，下面看看他的内容吧。

 1 Stack::Stack(int size)
 2 {
 3     stackArray=new int[size];
 4     for(int i=0;i<size;i++) stackArray[i]=0;
 5     count=0;
 6 }
 7 
 8 Stack::~Stack()
 9 {
10     delete []stackArray;
11 }
12 
13 bool Stack::CheckEmpty()
14 {
15     return (count==0);
16 }
17 
18 void Stack::Push(int ele)
19 {
20     stackArray[count]=ele;
21     ++count;
22 }
23 
24 int Stack::Pop()
25 {
26     --count;
27     int result=stackArray[count];
28     stackArray[count]=0;
29     return result;
30 }
31 
32 int Stack::GetValue(int Pos)
33 {     
34     return stackArray[count-Pos-1];
35 }
36 
37  
38 
39 
40 int Stack::GetCount() 
41 {
42     return count;
43 }

     对于压入我采用的是往数组的后面添加元素的方法，弹出是的话是将最后一个元素返回，然后设为0，同时堆栈的大小减一。同时，请大家注意，我的实现里面没有加入一些对于错误情况的判断，比如如果已经没有元素了，那么弹出是不允许的，如果元素已经满了，那么压入也是不允许的，这个部分我真心是想留给初学者做个练习，当然，如果你有兴趣的话。还有就是目前实现的堆栈只能压入整数，我没有使用模板或者typedef是因为我想还是简单点比较好。

     在大多数数据结构书里面堆栈应用举例就是随机生成多少个数，然后压入，弹出，看看输出结果是什么，我想的话，其实可以使用一个菜单，让使用者每次选压入还是弹出，然后观看变化，所以我想了这样两个函数。

 1 void printCube(int num)
 2 {
 3     cout<<"   "<<num<<"   "<<endl;
 4     cout<<"*******"<<endl; 
 5 }
 6 
 7 void menu()
 8 {
 9     cout<<"Please select one operation:"<<endl;
10     cout<<"1-Push"<<endl;
11     cout<<"2-Pop"<<endl;
12     cout<<"0-Quit"<<endl;
13 }

     当然，你可以在我的基础上扩展，那么主函数如下所示：

 1 void main()
 2 {
 3         int order,input;
 4     menu();
 5      int size=20;
 6       Stack s(size);
 7     while(cin>>order)
 8     {
 9       if(order==1)
10       {
11          cin>>input;
12          s.Push(input);
13       }
14       if(order==2)
15           s.Pop();
16       if(order==0)
17           break;
18 
19       for(int i=0;i<s.GetCount();i++)
20            printCube(s.GetValue(i));
21     }
22  
23     int i;
24     cin>>i;
25     
26 }

     首先，主函数做一些辅助工作，打印出选择菜单，然后我们申请一个大小为20的堆栈，等待用户的输入，初始界面如下：

     有两个命令，1是压入，2是弹出，那么我们来试一试吧，我们连续压入两个数，按下1，然后再按一个数，效果如下：

     可以看到3在2的上面，就像叠的盘子一样，再弹出一个数试试。

     可以看到堆栈中最上面的数已经被弹出了，这就是一个简单的堆栈，另外，后面的代码越来越大，我想将代码打包上传，这样下载完整的代码包可以保证整体性，对初学者更有帮助，想问问大家我应该往哪传啊？