数据结构(1)栈的自定义实现

Changwei | 9/15/2014 7:40:00 PM


栈和队列是最基础的数据结构,关于他们的特性和用法我们都已十分熟悉。今天我要描述的是如何自定义实现栈这种数据结构,这能够帮助我们深入地了解栈这种数据结构的原理,也能更好地研究其他数据结构类型。

概述:

自定义实现能够动态调整的泛型栈类型,并能够保持较好地性能。

 

实现:

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释放了,各位有解决办法的可以在下面评论中给出,谢谢。