算法浅谈：栈

　

栈

天跟大家聊聊栈，在程序设计中，栈的使用还是非常广泛的，比如有“括号匹配问题“，”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

三：常用操作

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

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

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

总的运行代码如下

View Code

相关阅读

【汇编】堆栈和画堆栈图

        根据咱们学汇编的经验呀，汇编用的最多的是寄存器和内存之间的不断相互传值传地址，井然有序。        然而，你知道

栈溢出例子理解

背景:最近在看一些教学视频，然后主讲人敲了一段栈溢出的代码。我当场蒙蔽了-。- ! 而且他也没有细讲原理，最为一名爱探险星人，我决定

JAVA堆栈

转自：https://blog.csdn.net/lk274857347/article/details/77512555基本概念1.寄存器：最快的存储区, 由编译器根据需求进行分配,我

【干货】堆栈溢出一般是什么原因?

堆栈是一个在计算机科学中经常使用的抽象数据类型。堆栈中的物体具有一个特性： 最后一个放入堆栈中的物体总是被最先拿出来， 这个特

Java堆栈简介

JAVA在程序运行时，在内存中划分5片空间进行数据的存储。分别是：1：寄存器。2：本地方法区。3：方法区。4：栈。5：堆。基本，栈stack和堆heap这