加载中...

第十天 栈

今天跟大家聊聊栈，在程序设计中，栈的使用还是非常广泛的，比如有“括号匹配问题“，”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;  public SeqStack(int lenth)
  13.         {
  14.             data = new T[lenth];
  15.         }
  16.     }
  17.     #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

总的运行代码如下 

  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<Student> seqStack = stackManager.SeqStackInit<Student>(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 < stackManager.SeqStackLen(seqStack); i++)
  37.             {
  38.                 Console.WriteLine("栈顶元素为：ID=" + seqStack.data[i].ID + ",Name=" + seqStack.data[i].Name + ",Age=" + seqStack.data[i].Age);
  39.             }
  40.  
  41.             Console.Read();
  42.         }
  43.     }
  44.  
  45.     #region 学生数据实体
  46.     /// <summary>
  47. /// 学生数据实体
  48. /// </summary>
  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.     /// <summary>
  61. /// 栈的数据结构
  62. /// </summary>
  63.     public class SeqStack<T>
  64.     {
  65.         public T[] data;
  66.  
  67.         /// <summary>
  68. /// 栈顶指针
  69. /// </summary>
  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.         /// <summary>
  83. /// 栈的初始化操作
  84. /// </summary>
  85. /// <typeparam name="T"></typeparam>
  86. /// <returns></returns>
  87.         public SeqStack<T> SeqStackInit<T>(int length)
  88.         {
  89.             SeqStack<T> seqStack = new SeqStack<T>(length);
  90.  
  91.             seqStack.top = -1;
  92.  
  93.             return seqStack;
  94.         }
  95.         #endregion
  96.  
  97.         #region 判断栈是否为空
  98.         /// <summary>
  99. /// 判断栈是否为空
  100. /// </summary>
  101. /// <typeparam name="T"></typeparam>
  102. /// <param name="seqStack"></param>
  103. /// <returns></returns>
  104.         public bool SeqStackIsEmpty<T>(SeqStack<T> seqStack)
  105.         {
  106.             return seqStack.top == -1;
  107.         }
  108.         #endregion
  109.  
  110.         #region 清空栈
  111.         /// <summary>
  112. /// 清空栈
  113. /// </summary>
  114. /// <typeparam name="T"></typeparam>
  115. /// <param name="seqStack"></param>
  116.         public void SeqStackClear<T>(SeqStack<T> seqStack)
  117.         {
  118.             seqStack.top = -1;
  119.         }
  120.         #endregion
  121.  
  122.         #region 栈是否已满
  123.         /// <summary>
  124. /// 栈是否已满
  125. /// </summary>
  126. /// <typeparam name="T"></typeparam>
  127. /// <param name="seqStack"></param>
  128.         public bool SeqStackIsFull<T>(SeqStack<T> seqStack)
  129.         {
  130.             return seqStack.top == seqStack.data.Length;
  131.         }
  132.         #endregion
  133.  
  134.         #region 入栈
  135.         /// <summary>
  136. /// 入栈
  137. /// </summary>
  138. /// <typeparam name="T"></typeparam>
  139. /// <param name="seqStack"></param>
  140. /// <param name="data"></param>
  141.         public void SeqStackPush<T>(SeqStack<T> 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.         /// <summary>
  152. /// 出栈
  153. /// </summary>
  154. /// <typeparam name="T"></typeparam>
  155. /// <param name="seqStack"></param>
  156. /// <returns></returns>
  157.         public T SeqStackPop<T>(SeqStack<T> 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.         /// <summary>
  170. /// 获取栈顶
  171. /// </summary>
  172. /// <typeparam name="T"></typeparam>
  173. /// <param name="seqStack"></param>
  174. /// <returns></returns>
  175.         public T SeqStackPeek<T>(SeqStack<T> seqStack)
  176.         {
  177.             if (SeqStackIsEmpty(seqStack))
  178.                 throw new Exception("栈已空");
  179.  
  180.             return seqStack.data[seqStack.top];
  181.         }
  182.         #endregion
  183.  
  184.         #region 获取栈中元素个数
  185.         /// <summary>
  186. /// 获取栈中元素个数
  187. /// </summary>
  188. /// <typeparam name="T"></typeparam>
  189. /// <param name="seqStack"></param>
  190. /// <returns></returns>
  191.         public int SeqStackLen<T>(SeqStack<T> seqStack)
  192.         {
  193.             return seqStack.top + 1;
  194.         }
  195.         #endregion
  196.     }
  197. }

还没有评论.