c#栈的实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› c#›C#教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

今天学习c#当中实现栈，学过C#的都知道，c#本身已经写好了栈和队列，我们可以直接用，这里自己实现以下，就是为了更深刻的理解。

首先说明线性表，栈、队列他们的数据元素以及数据元素之间的逻辑关系实际上都是相同的，不同的是线性表的操作不受限制，而栈和队列则受限制，栈的操作只能在一端进行，队列的扎入在一端进行，别的操作在另一端进行。

我们通常把表尾看做是栈顶，另一端是固定的叫栈底，栈中没有数据时我们称为空栈。

实现栈的代码

 public class SeqStack<T>
    {
        private int maxSize;// 顺序栈的容量

        public int MaxSize
        {
            get { return maxSize; }
            set { maxSize = value; }
        }
        public T[] data; // 数组，用于存储顺序栈中的数据元素
        private int top; // 指示顺序栈的栈顶

        public int Top
        {
            get { return top; }
        }
        //构造器
        public SeqStack(int size)
        {
            data = new T[size];
            maxSize = size;
            top = -1;
        } 
        // 定义索引器
        public T this[int index]
        {
            get { return data[index]; }
            set { data[index] = value; }
        }
        // 由于数组是 0 基数组，即数组的最小索引为 0，所以，顺序栈的长度就是数组中最后一个元素的索引 top 加 1
        public int GetLength()
        {
            return top + 1;
        }

        public bool IsEmpty()
        {
            if ( -1 == top )
            {
                return true;
            }
            return false;
        }
        public bool IsFull()
        {
            if ( top == maxSize - 1 )
            {
                return true;
            }
            return false;
        }
        public void Push( T item)
        {
            if ( IsFull() )
            {
                Console.WriteLine("栈已满，无法压栈");
                return;
            }
            data[++top] = item;
        }

        public T Pop()
        {
            if ( IsEmpty() )
            {
                Console.WriteLine("栈为空，无法弹栈");
                return default(T);
            }
            return data[top--];
        }

        public T Peek()
        {
            if ( IsEmpty() )
            {
                Console.WriteLine("栈为空，无法弹栈");
                return default(T);
            }
            return data[top];
        }
    }
    // 链表实现栈
    public class LinkStack<T>
    {
        private Node<T> top; // 栈顶指示器

        internal Node<T> Top 
        {
            get { return top; }
            set { top = value; }
        }
        private int nCount; //栈中结点的个数

        public int NCount
        {
            get { return nCount; }
            set { nCount = value; }
        }

        public LinkStack()
        {
            top = null;
            nCount = 0;
        }

        public int GetLength()
        {
            return nCount;
        }
        public bool IsEmpty()
        {
            if ( (top == null) && (0 == nCount))
            {
                return true;
            }
            return false;
        }
        public void Push(T item)
        {
            Node<T> p = new Node<T>(item);
            if ( top == null )
            {
                top = p;
            }
            else
            {
                p.Next = top;
                top = p;
            }
            nCount++;
        }

        public T Pop()
        {
            if ( IsEmpty() )
            {
                return default(T);
            }
            Node<T> p = top;
            top = top.Next;
            --nCount;
            return p.Data;
            
        }

        public T Peek()
        {
            if ( IsEmpty() )
            {
                return default(T);
            }
            return top.Data;
        }
    }

View Code

栈的引用举例

// 十进制数N转换为八进制数
        public static void Conversion(int n)
        {
            LinkStack<int> stack = new LinkStack<int>();
            while ( n > 0 )
            {
                stack.Push(n % 8);
                n = n >> 3;
            }
           while ( !stack.IsEmpty() )
           {
               Console.WriteLine( "{0}",stack.Pop() );
           }
           
        }

迷宫问题的应用

/*
 随机生成一个10*10的迷宫（可以用*表示起点，#表示终点，0代表不可以通过，1代表可以通过），假如[0,0] 为入口 [9,9] 为出口。
   （1）在控制台上显示该迷宫
   （2）利用结构求解该迷宫是否能抵达出口（入口与出口是否联通）。
   （3）如能抵达出口，输出从入口到出口的行走路径。
*/
// 我们首先创建一个Point类，来存放每个点的坐标，然后定义一个栈，来存放当前路径所经过的点
    class Point
    {
        public const int m = 10;
        public int x;
        public int y;
        public Point(int _x, int _y)
        {
            x = _x;
            y = _y;
        }
// 走迷宫
        public void GoPath( int[,] maze )
        {
            Point start = new Point(1, 1);// 迷宫起始点的坐标
            Point end = new Point(m-2, m - 2);// 迷宫终点的坐标

            int x = 1;// 初始点横坐标
            int y = 1;// 初始点纵坐标
            Stack<Point> path = new Stack<Point>();// 用栈来存储路径所通过点的坐标
            path.Push(start);// 将迷宫入口点的坐标压栈
            do 
            {
                bool flag = false;
                // 向右->下->左->上的顺序探测是否有通路
                if ( 0 == maze[x + 1, y] )
                {
                    maze[x + 1, y] = 2;// 有通过的路径点 ，避免以后重复走
                    path.Push(new Point(x + 1, y));// 把该点保存
                    flag = true;
                }
                // bottom
                else if ( 0 == maze[x, y + 1]  )
                {
                    maze[x, y + 1] = 2;
                    path.Push(new Point(x, y + 1));
                    flag = true;
                }
                // left
                else if (0 == maze[x - 1, y])
                {
                    maze[x - 1, y] = 2;
                    path.Push(new Point(x - 1, y));
                    flag = true;
                }

                // top
                else if ( 0 == maze[ x, y + 1 ])
                {
                    maze[x, y + 1] = 2;
                    path.Push(new Point(x, y + 1));
                    flag = true;
                }
                /*
                 如果四周都没有通路,  则将点从路径中删除，即弹出栈顶元素。 
                 如果此时栈为空，则表明弹出的是入口点，即此迷宫无解。 
                 否则后退一个点重新探测。
                 */
                if (!flag)
                {
                    path.Pop();
                    if ( 0 == path.Count )
                    {
                        Console.WriteLine(" 没有找到可以走出此迷宫的路径 ");
                        break;
                    }
                }
                // 读取栈顶元素并判断其是否是出口
                Point peek = path.Peek();
                if (peek.x == end.x && peek.y == end.y )
                {
                    Console.WriteLine( "已经找到出口" + path );
                    break;
                }
                // 如果栈顶元素不是出口，则以该元素为起点继续进行探测
                start = peek;
                x = start.x;
                y = start.y;
            } while ( path.Count > 0 );
        }
}

//        C#2.0提供了泛型的Stack<T>类，该类继承
//了 IEnumerable<T>、ICollection 和 IEnumerable 接口。下面的程序说明了泛型
//Stack<T>类的主要方法，并对在我们自定义的栈类中没有出现的成员方法进行了
//注释，关于泛型Stack<T>类的更具体的信息，读者可参考.NET Framework 的有
//关书籍。
public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable 
{ 
    public Stack(); 
    public Stack(int capacity); 
    public int Count {get;} 
    public void Clear(); 
    //确定某元素是否在Stack<T>中, 
    //如果在Stack<T>中找到item，则为true；否则为false。 
    public bool Contains(T item); 
    //从指定数组索引开始将Stack<T>复制到现有一维Array中。 
    public void CopyTo(T[] array, int arrayIndex); 
    //返回位于Stack<T>顶部的对象但不将其移除。 
    public T Peek(); 
    public T Pop(); 
    public void Push(T item); 
    //将Stack<T>复制到新数组中。 
    public T[] ToArray(); 
    //如果元素数小于当前容量的90%， 
    //将容量设置为Stack<T>中的实际元素数。 
    public void TrimExcess(); 
}