C#实现简单的栈和队列
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方法。由于使用的泛型，因此这应该是一个通用的排序方法，有两种方法可以实现：接口和委托，以后再写。
分类: .net 学习笔记
标签: c# , 面试 , 队列
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did46536