今天跟大家聊聊栈，在程序设计中，栈的使用还是非常广泛的，比如有“括号匹配问题“，”html结构匹配问题“。

所以说掌握了”栈“的使用，对我们学习算法还是很有帮助的。

一： 概念

         栈，同样是一种特殊的线性表，是一种Last In First Out（LIFO)的形式，现实中有很多这样的例子，

     比如：食堂中的一叠盘子，我们只能从顶端一个一个的取。

二：存储结构

        ”栈“不像”队列“，需要两个指针来维护，栈只需要一个指针就够了，这得益于栈是一种一端受限的线性表。

      这里同样用”顺序结构“来存储这个”栈“，top指针指向栈顶，所有的操作只能在top处。

代码段：

 1 #region 栈的数据结构
 2     /// 

 3 /// 栈的数据结构
 4 /// 
 5     public class SeqStack
 6     {
 7         public T[] data;
 8 
 9         /// 

10 /// 栈顶指针
11 /// 
12         public int top = -1;
13 
14         public SeqStack(int lenth)
15         {
16             data = new T[lenth];
17         }
18     }
19     #endregion

三：常用操作

        栈的操作有：①初始化栈，②入栈，③出栈，④获取栈顶。

1: 初始化栈

        这个还是比较简单的，初始化栈时，设置默认top指针为-1，这个就不用图来展示了。

代码段：

 1 #region 栈的初始化操作
 2         /// 

 3 /// 栈的初始化操作
 4 /// 
 5 /// 
 6 /// 
 7         public SeqStack SeqStackInit(int length)
 8         {
 9             SeqStack seqStack = new SeqStack(length);
10 
11             seqStack.top = -1;
12 
13             return seqStack;
14         }
15         #endregion

2：入栈

       这个操作主要就是做两件事情：① 将元素从栈顶压入，② top指针自增。

代码段：

 1 #region 入栈
 2         /// 

 3 /// 入栈
 4 /// 
 5 /// 
 6 /// 
 7 /// 
 8         public void SeqStackPush(SeqStack seqStack, T data)
 9         {
10             if (SeqStackIsFull(seqStack))
11                 throw new Exception("不好意思，栈溢出");
12 
13             seqStack.data[++seqStack.top] = data;
14         }
15         #endregion

3：出栈

      同样跟“入栈”类似，需要做两件事情，①干掉top处的元素，②top指针自减。

代码段

 1 #region 出栈
 2         /// 

 3 /// 出栈
 4 /// 
 5 /// 
 6 /// 
 7 /// 
 8         public T SeqStackPop(SeqStack seqStack)
 9         {
10             if (SeqStackIsEmpty(seqStack))
11                 throw new Exception("呜呜，栈已空");
12 
13             seqStack.data[seqStack.top] = default(T);
14 
15             return seqStack.data[--seqStack.top];
16         }
17         #endregion

4：获取栈顶元素

      这个很简单，跟“出栈”唯一不同的是不破坏栈顶元素，只是翻出来看看而已。

代码段

 1 #region 获取栈顶
 2         /// 

 3 /// 获取栈顶
 4 /// 
 5 /// 
 6 /// 
 7 /// 
 8         public T SeqStackPeek(SeqStack seqStack)
 9         {
10             if (SeqStackIsEmpty(seqStack))
11                 throw new Exception("栈已空");
12 
13             return seqStack.data[seqStack.top];
14         }
15         #endregion

总的运行代码如下

View Code

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 
  6 namespace SeqStack
  7 {
  8     class Program
  9     {
 10         static void Main(string[] args)
 11         {
 12             SeqStackClass stackManager = new SeqStackClass();
 13 
 14             SeqStack seqStack = stackManager.SeqStackInit(10);
 15 
 16             Console.WriteLine("********************  压入ID=1,ID=2,ID=3的元素  ***********************n");
 17             //压入ID=1,ID=2,ID=3的元素
 18             stackManager.SeqStackPush(seqStack, new Student() { ID = 1, Name = "一线码农", Age = 23 });
 19             stackManager.SeqStackPush(seqStack, new Student() { ID = 2, Name = "huangxincheng520", Age = 23 });
 20             stackManager.SeqStackPush(seqStack, new Student() { ID = 3, Name = "51cto", Age = 23 });
 21 
 22             Console.WriteLine(".... 压入成功，当前栈中元素有：" + stackManager.SeqStackLen(seqStack) + "个");
 23 
 24             Console.WriteLine("n******************  查看栈顶元素  ********************");
 25 
 26             var result = stackManager.SeqStackPeek(seqStack);
 27 
 28             Console.WriteLine("栈顶元素为：ID=" + result.ID + ",Name=" + result.Name + ",Age=" + result.Age);
 29 
 30             Console.WriteLine("n********************  弹出栈顶元素  ***********************");
 31 
 32             stackManager.SeqStackPop(seqStack);
 33 
 34             Console.WriteLine("n******************  查看栈中的元素  ********************");
 35 
 36             for (int i = 0; i 
 47 /// 学生数据实体
 48 /// 
 49     public class Student
 50     {
 51         public int ID { get; set; }
 52 
 53         public string Name { get; set; }
 54 
 55         public int Age { get; set; }
 56     }
 57     #endregion
 58 
 59     #region 栈的数据结构
 60     /// 

 61 /// 栈的数据结构
 62 /// 
 63     public class SeqStack
 64     {
 65         public T[] data;
 66 
 67         /// 

 68 /// 栈顶指针
 69 /// 
 70         public int top = -1;
 71 
 72         public SeqStack(int lenth)
 73         {
 74             data = new T[lenth];
 75         }
 76     }
 77     #endregion
 78 
 79     public class SeqStackClass
 80     {
 81         #region 栈的初始化操作
 82         /// 

 83 /// 栈的初始化操作
 84 /// 
 85 /// 
 86 /// 
 87         public SeqStack SeqStackInit(int length)
 88         {
 89             SeqStack seqStack = new SeqStack(length);
 90 
 91             seqStack.top = -1;
 92 
 93             return seqStack;
 94         }
 95         #endregion
 96 
 97         #region 判断栈是否为空
 98         /// 

 99 /// 判断栈是否为空
100 /// 
101 /// 
102 /// 
103 /// 
104         public bool SeqStackIsEmpty(SeqStack seqStack)
105         {
106             return seqStack.top == -1;
107         }
108         #endregion
109 
110         #region 清空栈
111         /// 

112 /// 清空栈
113 /// 
114 /// 
115 /// 
116         public void SeqStackClear(SeqStack seqStack)
117         {
118             seqStack.top = -1;
119         }
120         #endregion
121 
122         #region 栈是否已满
123         /// 

124 /// 栈是否已满
125 /// 
126 /// 
127 /// 
128         public bool SeqStackIsFull(SeqStack seqStack)
129         {
130             return seqStack.top == seqStack.data.Length;
131         }
132         #endregion
133 
134         #region 入栈
135         /// 

136 /// 入栈
137 /// 
138 /// 
139 /// 
140 /// 
141         public void SeqStackPush(SeqStack seqStack, T data)
142         {
143             if (SeqStackIsFull(seqStack))
144                 throw new Exception("不好意思，栈溢出");
145 
146             seqStack.data[++seqStack.top] = data;
147         }
148         #endregion
149 
150         #region 出栈
151         /// 

152 /// 出栈
153 /// 
154 /// 
155 /// 
156 /// 
157         public T SeqStackPop(SeqStack seqStack)
158         {
159             if (SeqStackIsEmpty(seqStack))
160                 throw new Exception("呜呜，栈已空");
161 
162             seqStack.data[seqStack.top] = default(T);
163 
164             return seqStack.data[--seqStack.top];
165         }
166         #endregion
167 
168         #region 获取栈顶
169         /// 

170 /// 获取栈顶
171 /// 
172 /// 
173 /// 
174 /// 
175         public T SeqStackPeek(SeqStack seqStack)
176         {
177             if (SeqStackIsEmpty(seqStack))
178                 throw new Exception("栈已空");
179 
180             return seqStack.data[seqStack.top];
181         }
182         #endregion
183 
184         #region 获取栈中元素个数
185         /// 

186 /// 获取栈中元素个数
187 /// 
188 /// 
189 /// 
190 /// 
191         public int SeqStackLen(SeqStack seqStack)
192         {
193             return seqStack.top + 1;
194         }
195         #endregion
196     }
197 }