首页 > 代码库 > 数据结构之堆栈
数据结构之堆栈
谈起堆栈，我想起兄弟。中国的汉语真是有意思，兄弟说的是弟，同理，堆栈，强调的是栈。栈是一种受限的线性表。我把数据结构的知识回顾下。数据结构是数据之间的关系。关系是普遍存在的。是不是有点哲学的味道。那么数据到底都有些什么关系呢？我们去银行办理业务，去坐车都需要排队，新生入学站成一排军训，如果我们把人看作数据，那么此时的人和人的位置关系，便是线性的。除了线性结构，还有什么结构呢？四世同堂的老人，他们一家人的血缘关系，如同一棵树。这便是树型结构。还有一种网状的结构，称为图，如城市的交通网。字典属于什么数据结构？它不是树，不是图，那它属于线性结构吗？字典显然是个集合，如果字典的key是线性关系，例如从1开始的编号，或者是a-z的字母，那么它能称得上线性关系吗？线性表是一种有限序列的集合。它是有顺序的。字典的数据项完全没有任何逻辑，它只与key有关系。
说了这么多，总结一下：数据之间的关系分为两种，逻辑关系和非逻辑关系如图所示：
今天我要说的栈是一种物理结构，它存储了一组线性元素，这组元素在操作上有后进先出的特性。因此可以看出，数据结构不仅研究数据之间的关系，以及存储，而且包括数据的操作。结构决定功能，正是有了栈这样的存储结构，因此，元素的操作上才有自己的特性。
接下来，我们看一个栈具体应用的例子：有一组有序数字，需要把相邻的数字序列取出来放在一起，零散的数字单独存放。例如有一组数字1,2,3,5,7,9,10,11，分组后的结果：（1,2,3），（5），（7），（9,10,11）。用程序如何实现呢？且看一般的实现方法，如下所示：
1 List<List<Int32>> sections = new List<List<int>>(); 2 sections.Add(new List<Int32>()); 3 //序号分组 4 for (int i = 0; i < numbers.Count; i++) 5 { 6 if (!((numbers[i + 1] - numbers[i]) == 1)) 7 { 8 sections[sections.Count - 1].Add(numbers[i]); 9 sections.Add(new List<Int32>());10 if (i + 1 == numbers.Count - 1)11 {12 sections[sections.Count - 1].Add(numbers[i + 1]);13 break;14 }15 continue;16 }17 18 sections[sections.Count - 1].Add(numbers[i]);19 if (i + 1 == numbers.Count - 1)20 {21 sections[sections.Count - 1].Add(numbers[i + 1]);22 break;23 }24 }
我们看看前辈写的这段代码，List嵌套，短短的程序，到处continue和break，这些都导致程序的可读性变差。
且看我的实现：
1 List<Stack<int>> list = new List<Stack<int>>(); 2 Stack<int> q = new Stack<int>(); 3 list.Add(q); 4 5 foreach (var n in numbers) 6 { 7 if (q.Count == 0) 8 { 9 //栈为空时，直接放进去10 q.Push(n);11 }12 else13 {14 //如果当前数字和栈中的数字没有关系时，新创建一个栈，否则直接放到栈中。15 if (n - 1 != list[list.Count - 1].Peek())16 {17 var q1 = new Stack<int>();18 q1.Push(n);19 list.Add(q1);20 }21 else22 {23 list[list.Count - 1].Push(n);24 }25 } 26 }
前辈的实现思路，是当前数字与下一个数字比较，看是否连续，我的实现思路，是当前数字与上一个数字比较。前辈的代码中，两次判断是否元素遍历到最后一个。我的只判断第一个栈是否有数据。如果集合的数量比较大，我可以更改我的代码如下：
1 List<Stack<int>> list = new List<Stack<int>>(); 2 Stack<int> q = new Stack<int>(); 3 list.Add(q); 4 if (numbers.Count > 0) 5 { 6 q.Push(numbers[0]); 7 } 8 9 for (int i = 1; i < numbers.Count; i++)10 {11 //如果当前数字和栈中的数字没有关系时，新创建一个栈，否则直接放到栈中。12 if (numbers[i] - 1 != list[list.Count - 1].Peek())13 {14 var q1 = new Stack<int>();15 q1.Push(numbers[i]);16 list.Add(q1);17 }18 else19 {20 list[list.Count - 1].Push(numbers[i]);21 }22 }
此时，前辈和我的程序运行结果如图：
你或许对这两幅图，觉得不就一样嘛，一个是是躺着的，一个是站起来的。但是，别忘了，我的结果图是可以想象成家里的桶，每个桶里装的是连续的数字。那你或许会说，前辈的结果图可以想象为抽屉，每个抽屉装的是连续的数字。好了，说到这儿，还真的没法区分孰优孰劣。那么我们看看，分组后这些数字的应用，先看前辈的：
1 //序号拼接 2 for (int i = 0; i < sections.Count; i++) 3 { 4 String seq = ""; 5 6 if (sections[i].Count >= intextCodeOrder.CitationNumber) 7 seq = "-"; 8 else if (sections[i].Count > 1) 9 {10 seq = ",";11 }12 else13 {14 if (!sbNumber.ToString().Contains(sections[i][0].ToString()))15 sbNumber.AppendFormat("{0},", sections[i][0]);16 continue;17 }18 sbNumber.AppendFormat("{0}{1}{2},", sections[i][0], seq, sections[i][sections[i].Count - 1]);19 }
解释下这段代码：如果连续的数字个数超过了某个值，用 “-” 号连接起来，否则的话用 “，”号连接。
再看看我的代码：
1 foreach (var stack in list) 2 { 3 if (stack.Count == 1) 4 { 5 sbNumber.AppendFormat("{0},", Mapping(stack.Pop())); 6 } 7 else 8 { 9 if (stack.Count >= intextCodeOrder.CitationNumber)10 join = "-";11 else if (stack.Count > 1)12 {13 join = ",";14 }15 int lastNumber = stack.Pop();16 int firstNumber = 0;17 18 //根据栈先进后出的特性，取得第一个进栈的数字19 while (stack.Count > 0)20 {21 firstNumber = stack.Pop();22 }23 sbNumber.AppendFormat("{0}{1}{2},", Mapping(firstNumber), join, Mapping(lastNumber));24 }25 }
看到这里，发现我写的这段代码，有个小瑕疵，在找第一个进栈的数字，需要循环出栈。这个在数据量少的情况下，不影响系统性能，在数据量大的情况下，就该考虑其它的存储结构了。本例子中，采用栈的优点是可读性强，分组的时候，程序可以写得简短明了。而且还避免了集合的索引带来的问题，经常要判断，以免出界。
当然栈的应用是十分广泛的，我只是列举了一个列子罢了。在程序的递归调用上使用了栈，在浏览器以及ps的历史记录中发挥着作用。
数据结构之堆栈