• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C#数据结构-栈

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

理论基础:

      栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top),另一端是固定的,叫栈底(Bottom)。当栈中没有数据元素时叫空栈(Empty Stack)。

      栈可以分为顺序栈和链栈。

      用一片连续的存储空间来存储栈中的数据元素,这样的栈称为顺序栈(Sequence Stack)。类似于顺序表,用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为0的端,top随着插入和删除而变化,当栈为空时,top=-1。

      链栈通常用单链表来表示,它的实现是单链表的简化。所以,链栈结点的结构与单链表结点的结构一样,如图3.3所示。由于链栈的操作只是在一端进行,为了操作方便,把栈顶设在链表的头部,并且不需要头结点。

 

C#实现:

     顺序栈

    1 接口

       用泛型接口来表示栈,接口中的方法成员表示基本操作

   1:   public interface IStack<T>
   2:      {
   3:          
   4:          /// <summary>
   5:          /// 求栈的长度
   6:          /// </summary>
   7:          /// <returns></returns>
   8:          int GetLength();
   9:          /// <summary>
  10:          /// 判断栈是否为空
  11:          /// </summary>
  12:          /// <returns></returns>
  13:          bool IsEmpty();
  14:          /// <summary>
  15:          /// 判断栈是否已满
  16:          /// </summary>
  17:          /// <returns></returns>
  18:          bool IsFull();
  19:          /// <summary>
  20:          /// 清空操作
  21:          /// </summary>
  22:          void Clear();
  23:          /// <summary>
  24:          /// 入栈操作
  25:          /// </summary>
  26:          /// <param name="item"></param>
  27:          void Push(T item);
  28:          /// <summary>
  29:          /// 出栈操作
  30:          /// </summary>
  31:          /// <returns></returns>
  32:          T Pop();
  33:          /// <summary>
  34:          /// 取栈元素
  35:          /// </summary>
  36:          /// <param name="index"></param>
  37:          /// <returns></returns>
  38:          T GetElement(int index);
  39:         
  40:      }

     2 实现

      下面实现的代码没有经过测试,不知道正确与否,有兴趣的朋友试试。

   1:  public class SeqStack<T> : IStack<T>
   2:      {
   3:          private int maxsize;        //顺序栈的容量
   4:          private T[] data;           //数组,用于存储顺序栈中的数据元素
   5:          private int top;            //栈顶
   6:   
   7:          //索引器
   8:          public T this[int index]
   9:          {
  10:              get
  11:              {
  12:                  return data[index];
  13:              }
  14:              set
  15:              {
  16:                  data[index] = value;
  17:              }
  18:          }
  19:          public int MaxSize
  20:          {
  21:              get
  22:               {
  23:                   return maxsize;
  24:              }
  25:              set
  26:              {
  27:                  maxsize = value;
  28:              }
  29:          }
  30:   
  31:          public int Top
  32:          {
  33:              get
  34:              {
  35:                  return top;
  36:              }
  37:          }
  38:   
  39:          public SeqStack(int size)
  40:          {
  41:              data = new T[size];
  42:              maxsize = size;
  43:              top = -1;
  44:          }
  45:   
  46:          /// <summary>
  47:          /// 求栈的长度
  48:          /// </summary>
  49:          /// <returns></returns>
  50:          public int GetLength()
  51:          {
  52:              return top + 1;
  53:          }
  54:          /// <summary>
  55:          /// 判断栈是否为空
  56:          /// </summary>
  57:          /// <returns></returns>
  58:          public bool IsEmpty()
  59:          {
  60:              if (top == -1)
  61:              {
  62:                  return true;
  63:              }
  64:              else
  65:              {
  66:                  return false;
  67:              }
  68:          }
  69:          /// <summary>
  70:          /// 判断栈是否已满
  71:          /// </summary>
  72:          /// <returns></returns>
  73:          public bool IsFull()
  74:          {
  75:              if (top == maxsize - 1)
  76:              {
  77:                  return true;
  78:              }
  79:              else
  80:              {
  81:                  return false;           
  82:               }
  83:          }
  84:          /// <summary>
  85:          /// 清空操作
  86:          /// </summary>
  87:         public void Clear()
  88:          {
  89:              top = -1;
  90:          }
  91:          /// <summary>
  92:          /// 入栈操作
  93:          /// </summary>
  94:          /// <param name="item"></param>
  95:         public  void Push(T item)
  96:          {
  97:              if (IsFull())
  98:              {
  99:                  Console.Write("Stack is full");
 100:                  return;
 101:              }
 102:              data[++top] = item;
 103:          }
 104:          /// <summary>
 105:          /// 出栈操作
 106:          /// </summary>
 107:          /// <returns></returns>
 108:         public  T Pop()
 109:          {
 110:              if (IsEmpty())
 111:              {
 112:                  Console.Write("Stack is empty");
 113:                  return default(T);
 114:              }
 115:              T outEle = data[top];
 116:              --top;
 117:              return outEle;
 118:          }
 119:          /// <summary>
 120:          /// 取栈顶元素
 121:          /// </summary>
 122:          /// <param name="index"></param>
 123:          /// <returns></returns>
 124:          public T GetElement(int index)
 125:          {
 126:              if (IsEmpty())
 127:              {
 128:                  Console.Write("Stack is empty");
 129:                  return default(T);
 130:              }
 131:              if (index < 0 && index > top + 1)
 132:              {
 133:                  Console.Write("index is error");
 134:                  return default(T);
 135:              }
 136:              return data[index - 1];
 137:          }
 138:      }

   由于链栈的操作与单链表很相似,这里就不说明代码,有兴趣的朋友可以写出来,供大家分享。

C#中的栈:

    C#2.0以下版本只提供了非泛型的Stack类,该类继承了ICollection、IEnumerable和ICloneable接口。

    C#2.0提供了泛型的Stack<T>类,该类继承了IEnumerable<T>、ICollection和IEnumerable接口,关于泛型Stack<T>类的更具体的信息,读者可参考.NET Framework的有关书籍


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#Windows服务的安装和卸载批处理发布时间:2022-07-18
下一篇:
C#私有的构造函数的作用发布时间:2022-07-18
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap