算法系列15天速成——第十天 栈
今天跟大家聊聊栈,在程序设计中,栈的使用还是非常广泛的,比如有“括号匹配问题“,”html结构匹配问题“。
所以说掌握了”栈“的使用,对我们学习算法还是很有帮助的。
一: 概念
栈,同样是一种特殊的线性表,是一种Last In First Out(LIFO)的形式,现实中有很多这样的例子,
比如:食堂中的一叠盘子,我们只能从顶端一个一个的取。
二:存储结构
”栈“不像”队列“,需要两个指针来维护,栈只需要一个指针就够了,这得益于栈是一种一端受限的线性表。
这里同样用”顺序结构“来存储这个”栈“,top指针指向栈顶,所有的操作只能在top处。
代码段:
1 #region 栈的数据结构
2 /// <summary>
3 /// 栈的数据结构
4 /// </summary>
5 public class SeqStack<T>
6 {
7 public T[] data;
8
9 /// <summary>
10 /// 栈顶指针
11 /// </summary>
12 public int top = -1;
13
14 public SeqStack(int lenth)
15 {
16 data = new T[lenth];
17 }
18 }
19 #endregion
www.zzzyk.com
三:常用操作
栈的操作有:①初始化栈,②入栈,③出栈,④获取栈顶。
1: 初始化栈
这个还是比较简单的,初始化栈时,设置默认top指针为-1,这个就不用图来展示了。
代码段:
1 #region 栈的初始化操作
2 /// <summary>
3 /// 栈的初始化操作
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <returns></returns>
7 public SeqStack<T> SeqStackInit<T>(int length)
8 {
9 SeqStack<T> seqStack = new SeqStack<T>(length);
10
11 seqStack.top = -1;
12
13 return seqStack;
14 }
15 #endregion
2:入栈
这个操作主要就是做两件事情:① 将元素从栈顶压入,② top指针自增。
代码段:
1 #region 入栈
2 /// <summary>
3 /// 入栈
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <param name="data"></param>
8 public void SeqStackPush<T>(SeqStack<T> 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 /// <summary>
3 /// 出栈
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <returns></returns>
8 public T SeqStackPop<T>(SeqStack<T> 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
www.zzzyk.com
4:获取栈顶元素
这个很简单,跟“出栈”唯一不同的是不破坏栈顶元素,只是翻出来看看而已。
代码段
1 #region 获取栈顶
2 /// <summary>
3 /// 获取栈顶
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="seqStack"></param>
7 /// <returns></returns>
8 public T SeqStackPeek<T>(SeqStack<T> seqStack)
9 {
10 if (SeqStackIsEmpty(seqStack))
11 throw new Exception("栈已空");
12
13 return seqStack.data[seqStack.top];
14 }
15 #endregion
www.zzzyk.com
总的运行代码如下
View Cod
补充:软件开发 , 其他 ,