当前位置:软件学习 > 其它软件 >>

算法系列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

补充:软件开发 , 其他 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,