首页 > 代码库 > 数据结构（1）栈的自定义实现
数据结构（1）栈的自定义实现
栈和队列是最基础的数据结构，关于他们的特性和用法我们都已十分熟悉。今天我要描述的是如何自定义实现栈这种数据结构，这能够帮助我们深入地了解栈这种数据结构的原理，也能更好地研究其他数据结构类型。
概述：
自定义实现能够动态调整的泛型栈类型，并能够保持较好地性能。
实现：
1.首先我们实现的是一种定容泛型栈类型，此种栈创建后，大小固定，十分容易实现。
public class FixedCapacityStack<T> { private T[] a; private int N; public FixedCapacityStack(int cap) { a = new T[cap]; } public bool isEmpty() { return N == 0; } public int Size() { return N; } public void Push(T item) { a[N++] = item; } public T Pop() { return a[--N]; }
}
这段C#代码成功实现了一个泛型栈，但是其容量是固定的，当他的大小远远小于或者大于容量时，就会造成内存资源浪费和异常。这就要求我们实现可变的，灵活地栈类型。
2.接下来我们实现可变容的泛型栈类型，这样我们就可以达到动态缩放其大小。
public class FixedCapacityStack<T> { private T[] a; private int N; public FixedCapacityStack(int cap) { a = new T[cap]; } public bool isEmpty() { return N == 0; } public void Resize(int max) { T[] temp = new T[max]; for (int i = 0; i < a.Length; i++) temp[i] = a[i]; a = temp; } public int Size() { return N; } public void Push(T item) { if (N == a.Length) Resize(2 * a.Length); a[N++] = item; } public T Pop() { T item= a[--N]; if (N>0&&N == a.Length / 4) Resize(a.Length / 2); return item; } }
3.进一步实现可迭代的栈类型,能够按照设计意图实现栈类型迭代的特性。 public class FixedCapacityStack<T>:IEnumerable
{ private T[] a; private int N; public FixedCapacityStack(int cap) { a = new T[cap]; } public bool isEmpty() { return N == 0; } public void Resize(int max) { T[] temp = new T[max]; int min=Min(a.Length,temp.Length); for (int i = 0; i < min; i++) temp[i] = a[i]; a = temp; } public int Min(int x, int y) { if (x < y) return x; else return y; } public int Size() { return N; } public void Push(T item) { if (N == a.Length) Resize(2 * a.Length); a[N++] = item; } public T Pop() { T item= a[--N];
a[N]=null; if (N>0&&N == a.Length / 4) Resize(a.Length / 2); return item; } public IEnumerator GetEnumerator() { for (int i = a.Length-1; i >=0; i--) { yield return a[i]; } } }
应用：
我们可以通过实际调用测试其实际运行效果，代码如下：
class Program { static void Main(string[] args) { /* string testExpress = "(1+((2+3)*(4*5)))"; Console.WriteLine(Evaluate(testExpress));*/ FixedCapacityStack<string> s = new FixedCapacityStack<string>(100); for (int i = 0; i < 150; i++) s.Push(i.ToString()); Console.WriteLine(s.Size()); for(int j=0;j<120;j++) s.Pop(); foreach (var item in s) { Console.WriteLine(item); } Console.WriteLine(s.Size()); }}
至此我们实现了一个可迭代的可变容的范型栈类型，这样再来理解和使用栈类型，势必会有更清晰的认识。
class Program { static void Main(string[] args) { /* string testExpress = "(1+((2+3)*(4*5)))"; Console.WriteLine(Evaluate(testExpress));*/ FixedCapacityStack<string> s = new FixedCapacityStack<string>(100); for (int i = 0; i < 150; i++) s.Push(i.ToString()); Console.WriteLine(s.Size()); for(int j=0;j<120;j++) s.Pop(); foreach (var item in s) { Console.WriteLine(item); } Console.WriteLine(s.Size()); }}
这里我有一个问题，范型数组没法讲其值改为null么？这样也就没法进行Pop释放了，各位有解决办法的可以在下面评论中给出，谢谢。
数据结构（1）栈的自定义实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。