你的位置:首页 > ASP.net教程

[ASP.net教程]C#中泛型容器StackT的用法,以及借此实现撤销/重做功能


 

.Net为我们提供了众多的泛型集合。比如,Stack<T>先进后出,Queue<T>先进先出,List<T>集合元素可排序,支持索引,LinkedList<T>,双向链表的泛型实现,不支持索引;ISet<T>不允许被复制,他有2个实现,一个是HashSet<T>,不维持集合元素的排序,另一个是SortedSet<T>,支持集合元素的排序;IDictionary<TKey, TValue>是一个字典集合的泛型接口,SortedList<TKey,TValue>实现了IDictionary<TKey, TValue>,但同时也是集合,维持集合元素的排序,支持按键或按值索引。

 

本篇体验Stack<T>的用法。

 

基本用法

 

Stack<T>是Stack的泛型实现,提供了若干方法和属性,比如入栈、出栈、查看栈顶元素,查看栈内集合元素数量,等等。栈的最大特点是先进后出,可以把栈想像成一堆叠起来的盘子,入栈就是把一个个盘子放到最上面,出栈就是从最上面把盘子拿掉。用法比较简单:

 

  class Program
  {
    static void Main(string[] args)
    {
      var customer1 = new Customer() {ID = 1, Name = "张三", Gender = "男"};
      var customer2 = new Customer() { ID = 2, Name = "李四", Gender = "男" };
      Stack<Customer> stackCustomers = new Stack<Customer>();
      //入栈
      stackCustomers.Push(customer1);
      stackCustomers.Push(customer2);
      //查看栈顶元素
      Customer topCustomer = stackCustomers.Peek();
      Console.WriteLine("栈顶元素是:" + topCustomer.Name);
      //遍历所有栈内元素
      foreach (var customer in stackCustomers)
      {
        Console.WriteLine("id is {0},name is {1}", customer.ID, customer.Name);
      }
      //出栈
      Customer outCustomer = stackCustomers.Pop();
      Console.WriteLine("正在出栈的是:" + outCustomer.Name);
      Console.WriteLine("当前栈内元素数量为:" + stackCustomers.Count);
      Console.ReadKey();
    }
  }
  public class Customer
  {
    public int ID { get; set; }
    public string Name { get; set; }
    public string Gender { get; set; }
  }

 

临摹一个泛型Stack<T> 

 

泛型Stack类内部维护这一个泛型数组和索引指针,且指针的初始位置是-1。

 

入栈就是把指针往前提一位,并把入栈元素赋值给该栈内位置。另外,入栈要考虑是否达到容量上限,如果达到就要给数组扩容。

 

出栈就是让当前栈位置的元素值为入栈类型的默认值,并大指针后退一位。

 

获取栈顶元素就是获取栈当前索引位置对应的元素。

 

  public class MyStack<T>
  {
    //维护T类型的数组
    private T[] _elements;
    protected T[] Elements
    {
      get { return _elements; }
      set { _elements = value; }
    }
    public MyStack()
    {
      _capacity = 5;//初始值
      Elements = new T[Capacity];
    }
    public MyStack(int capacity)
    {
      Capacity = capacity;
      Elements = new T[Capacity];
    }
    //指针
    private int _index = -1;
    public int Index
    {
      get { return _index; }
      set { _index = value; }
    }
    //容量
    private int _capacity;
    public int Capacity
    {
      get { return _capacity; }
      set { _capacity = value; }
    }
    //长度=索引+1
    public int Length
    {
      get { return Index + 1; }
    }
    //入栈
    public void Push(T element)
    {
      if (this.Length == Capacity)
      {
        IncreaseCapacity();
      }
      Index++;
      Elements[Index] = element;
    }
    //出栈
    public T Pop()
    {
      if (this.Length < 1)
      {
        throw new InvalidOperationException("栈内已空");
      }
      T element = Elements[Index];
      //原先位置元素变成默认值
      Elements[Index] = default(T);
      //索引减一
      Index--;
      return element;
    }
    //获取栈顶元素
    public T Peek()
    {
      if (this.Length < 1)
      {
        throw new InvalidOperationException("栈内已空");
      }
      return Elements[Index];
    }
    private void IncreaseCapacity()
    {
      Capacity++;
      Capacity *= 2;
      //创建新的T类型数组
      T[] newElements = new T[Capacity];
      //把原先的数组复制到新的数组中来
      Array.Copy(Elements, newElements, Elements.Length);
      Elements = newElements;
    }
  }

 

现在,在客户端,实施一系列的入栈和出栈操作。

 

    static void Main(string[] args)
    {
      //创建泛型Stack实例
      MyStack<int> myStack = new MyStack<int>();
      //遍历10次入栈
      for (int i = 0; i < 10; i++)
      {
        Console.WriteLine(i + "开始入栈");
        myStack.Push(i);
        Console.WriteLine("当前栈的长度是:" + myStack.Length);
      }
      
      //遍历10次出栈
      for (int i = 0; i < 10; i++)
      {
        Console.WriteLine("当前出栈的是" + myStack.Peek());
        myStack.Pop();
        Console.WriteLine("当前栈的长度是:" + myStack.Length);
      }
      //所有出栈结束,再查看栈顶元素抛异常
      try
      {
        myStack.Peek();
      }
      catch (InvalidOperationException ex)
      {
        Console.WriteLine(ex.Message);
      }
      //所有出栈结束,再出栈抛异常
      try
      {
        myStack.Pop();
      }
      catch (InvalidOperationException ex)
      {
        Console.WriteLine(ex.Message);
      }
      Console.ReadKey();
    }

 

其实,泛型Stack<T>的内部也是维护着一个数组,数组的容量是动态变化的,这一点很像List<T>,就像这里提到的。

 

使用泛型Stack<T>实现"撤销/重做"操作

 

首先,操作或撤销操作是针对某种类型的撤销或重做,提炼出一个接口。

 

  public interface ICommand<T>
  {
    T Do(T input);
    T Undo(T input);
  }

 

假设,这里想实现对整型数的"撤销/重做"操作。

 

  public class AddIntCommand : ICommand<int>
  {
    private int _value;
    public int Value
    {
      get { return _value; }
      set { _value = value; }
    }
    public AddIntCommand()
    {
      _value = 0;
    }
    public AddIntCommand(int value)
    {
      _value = value;
    }
    //执行操作
    public int Do(int input)
    {
      return input + _value;
    }
    //撤销操作
    public int Undo(int input)
    {
      return input - _value;
    }
  }

 

接下来,需要一个泛型类来管理所有撤销或操作命令,把这些命令放在Stack<ICommand<T>>泛型集合中。

 

  //使用泛型Stack实现撤销或重做
  public class UndoRedoStack<T>
  {
    private Stack<ICommand<T>> _undo;//有关撤销的泛型stack
    private Stack<ICommand<T>> _redo;//有关重做的泛型stack
    public UndoRedoStack()
    {
      Reset();
    }
    //记录撤销的数量
    public int UndoCount
    {
      get { return _undo.Count; }
    }
    //记录重做的数量
    public int RedoCount
    {
      get { return _redo.Count; }
    }
    //恢复到出厂设置
    public void Reset()
    {
      _undo = new Stack<ICommand<T>>();
      _redo = new Stack<ICommand<T>>();
    }
    //执行操作
    public T Do(ICommand<T> cmd, T input)
    {
      T output = cmd.Do(input);
      //把刚才的命令放入有关撤销的stack中
      _undo.Push(cmd);
      //一旦启动一个新命令,有关重做的stack清空
      _redo.Clear();
      return output;
    }
    //撤销操作
    public T Undo(T input)
    {
      if (_undo.Count > 0)
      {
        //出栈
        ICommand<T> cmd = _undo.Pop();
        T output = cmd.Undo(input);
        _redo.Push(cmd);
        return output;
      }
      else
      {
        return input;
      }
    }
    //重做操作
    public T Redo(T input)
    {
      if (_redo.Count > 0)
      {
        ICommand<T> cmd = _redo.Pop();
        T output = cmd.Do(input);
        _undo.Push(cmd);
        return output;
      }
      else
      {
        return input;
      }
    }
  }

 

最后,在客户端按如下调用:

 

    static void Main(string[] args)
    {
      UndoRedoStack<int> intCalulator = new UndoRedoStack<int>();
      int count = 0;
      count = intCalulator.Do(new AddIntCommand(10), count);
      count = intCalulator.Do(new AddIntCommand(20), count);
      Console.WriteLine("第一次计算的值为:{0}",count);
      //执行撤销操作一次
      count = intCalulator.Undo(count);
      Console.WriteLine("第二次计算的值为:{0}",count);
      Console.ReadKey();
    }  


 

参考资料:

http://brendan.enrick.com/post/Simple-C-Stack-Implementation

http://www.cambiaresearch.com/articles/82/generic-undoredo-stack-in-csharp