C#实现简单的栈和队列
C#提供了栈和队列，我们自己也可以尝试简单实现。
而且这可以作为一个很好的面试题，主要考察c#基础、类的设计以及数据结构。根据不同的职位需求可以考察选择不同的考察难度和角度。4年前我第一次参加面试并进现在的公司，职位基本是公司的最低岗位了。当时面的题目就是：实现一个栈。
简单的实现如下（考虑到顺序结构实现队列比较麻烦，采用链式结构）：
首先是结点类的实现：
1 // 结点类 2 // 注意应该使用泛型 3 public class MyNode<T> 4 { 5 // 存储的数据 6 public T Data 7 { 8 get { return _data; } 9 set { _data = value; } 10 } 11 12 // 指向下一个结点 13 public MyNode<T> next { get { return _next; } set { _next = value; } } 14 15 //构造函数，不提供无参版本 16 public MyNode(T data) 17 { 18 _data = data; 19 _next = null; 20 } 21 22 // 私有字段 23 private T _data; 24 private MyNode<T> _next; 25 }
然后抽象一个简单的父类：
1 // 为栈和队列提取一些通用的成员，抽象出一个父类，此处用接口还是抽象函数？ 2 // 在C#中Stack和Queue继承自两个接口：IEnumerable<T>, ICollection 3 // 但是作为简单的实现（特别是作为面试题答案），还是写成抽象类比较好，原因有二： 4 // 1. 可以在抽象类中实现一些通用方法，子类只需要继承就可以直接用，可以简化代码 5 // 2. 抽象出来的父类，和子类Stack、Queue可以看做“is-a”的关系。 6 // 当然也可以是非抽象的普通类，但是处于“不能实例化”的考虑，应该是抽象的 7 // 注意使用泛型 8 public abstract class AbstactList<T> 9 { 10 // 头结点，其后才是第一个结点 11 // 注意应该是protected，对外是不可见的 12 protected MyNode<T> Header { get; set; } 13 // 尾结点，即是最后一个结点 14 protected MyNode<T> Tail { get; set; } 15 // 当前结点个数，注意是只读属性 16 public int NoteCount { get { return _noteCount; } } 17 18 // 构造函数，初始化头结点和结点个数 19 public AbstactList() 20 { 21 // 注意此处default(T)的使用 22 Header = new MyNode<T>(default(T)); 23 Tail = Header; 24 _noteCount = 0; 25 } 26 27 // “出的操作”，对于栈和队列都是一样的，所以可以写在父类里 28 // 注意应该从“头”端出，时间复杂度为O（1） 29 // 如果从“尾”端出，则会造成时间复杂度为O（n） 30 protected T Out() 31 { 32 // 注意判空，只要一个条件就可以了，将所有的条件都写在这里可以有利于在测试的时候检测出bug 33 if (Header.next == null && _noteCount == 0 && NoteCount == 0 && IsEmpty()) 34 { 35 throw new InvalidOperationException("Is empty!"); 36 } 37 38 MyNode<T> outNode = Header.next; 39 Header.next = Header.next.next; 40 _noteCount--; 41 return outNode.Data; 42 } 43 44 // 判空 45 public bool IsEmpty() 46 { 47 return _noteCount == 0 ? true : false; 48 } 49 50 // 对于“出”的操作，栈和队列是有区别的，所以申明成抽象方法 51 // 到子类中去具体实现 52 protected abstract void In(T NodeData); 53 54 // 子类中还要用到，所以是Protected 55 protected int _noteCount; 56 }
栈的具体实现：
1 // 栈的实现，继承自抽象类 2 public class MyStack<T> : AbstactList<T> 3 { 4 // 实现“进”的方法，在“头”端 5 // 由于实现抽象类方法的当前方法默认是虚的，所以无法设为private 6 protected override void In(T NodeData) 7 { 8 MyNode<T> Node = new MyNode<T>(NodeData); 9 Node.next = Header.next; 10 Header.next = Node; 11 _noteCount++; 12 } 13 14 // 进栈，只是将操作改个名字 15 public void Push(T NodeData) 16 { 17 In(NodeData); 18 } 19 20 // 出栈，只是将操作改个名字 21 public T Pop() 22 { 23 return Out(); 24 } 25 }
队列的实现：
1 // 队列的实现，继承自抽象类 2 public class MyQueue<T> : AbstactList<T> 3 { 4 // 实现“进”的方法，在“头”端 5 // 由于实现抽象类方法的当前方法默认是虚的，所以无法设为private 6 protected override void In(T NodeNode) 7 { 8 MyNode<T> Node = new MyNode<T>(NodeNode); 9 Tail.next = Node; 10 Tail = Node; 11 _noteCount++; 12 } 13 14 public void EnQue(T NodeData) 15 { 16 In(NodeData); 17 } 18 19 public T DeQue() 20 { 21 return Out(); 22 } 23 }
单元测试：
对栈和队列的单元测试
1 [TestClass] 2 public class UnitTest1 3 { 4 [TestMethod] 5 public void StackTest() 6 { 7 MyStack<char> charStack = new MyStack<char>(); 8 Assert.IsTrue(charStack.IsEmpty()); 9 charStack.Push('a'); 10 Assert.IsFalse(charStack.IsEmpty()); 11 charStack.Push('b'); 12 Assert.AreEqual(charStack.Pop(), 'b'); 13 charStack.Push('c'); 14 Assert.AreEqual(charStack.NoteCount,2); 15 Assert.AreEqual(charStack.Pop(), 'c'); 16 Assert.AreEqual(charStack.Pop(), 'a'); 17 Assert.IsTrue(charStack.IsEmpty()); 18 19 try 20 { 21 charStack.Pop(); 22 } 23 catch (Exception ex) 24 { 25 Assert.IsInstanceOfType(ex,typeof(InvalidOperationException)); 26 } 27 } 28 29 [TestMethod] 30 public void QueueTest() 31 { 32 MyQueue<int> intQueue = new MyQueue<int>(); 33 Assert.IsTrue(intQueue.IsEmpty()); 34 intQueue.EnQue(1); 35 intQueue.EnQue(2); 36 Assert.AreEqual(intQueue.DeQue(), 1); 37 intQueue.EnQue(3); 38 Assert.AreEqual(intQueue.NoteCount,2); 39 Assert.AreEqual(intQueue.DeQue(), 2); 40 Assert.AreEqual(intQueue.DeQue(), 3); 41 Assert.IsTrue(intQueue.IsEmpty()); 42 43 try 44 { 45 intQueue.DeQue(); 46 } 47 catch (Exception ex) 48 { 49 Assert.IsInstanceOfType(ex, typeof(InvalidOperationException)); 50 } 51 } 52 }
后记：
作为更高难度，还可以加一个要求：实现Sort方法。由于使用的泛型，因此这应该是一个通用的排序方法，有两种方法可以实现：接口和委托，以后再写。