用顺序栈解决堆栈的编程问题

àì夳堔傛蜴生んèń 2021-09-18 03:38 277阅读 0赞

用顺序栈解决堆栈的编程问题：

堆栈（Stack）是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入，删除操作的一端称为栈顶，最下面的那一端称为栈底。

栈的主要特点：先进后出。

堆栈是一种特殊的线性表，所以线性表的两种特殊存储结构--顺序存储结构和链式存储结构也同样适用于堆栈。

栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1。

数组的元素类型使用泛型，以实现不同数据类型的线性栈间代码的重用；因为是用数组存储顺序栈，所以应预先为顺序栈分配最大存储空间，用字段maxsize来表示顺序栈的最大长度容量；由于栈顶元素经常变动，需要设置一个变量top表示栈顶，top的范围是0到maxsize-1，如果顺序栈为空，top=-1。

顺序栈的结构示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70][]

代码实现：

using System;
    
    namespace 用顺序栈解决堆栈的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
    
        interface IStack<T>
        {
            void Push(T elem);//入栈
            T Pop();//出栈
            T GetTop();//取栈顶
            int GetLength();//求栈长
            bool IsEmpty();//判断栈是否为空
            void Clear();//清空操作
        }
    
        class SeqStack<T>:IStack <T>
        {
            private int maxsize;//顺序栈的容量
            private T[] data;//数组，用于存储顺序栈中的数据元素
            private int top;//指示顺序栈的栈顶
    
            /// <summary>
            /// 容量属性
            /// </summary>
            public int Maxsize
            {
                get { return maxsize; }
                set { maxsize = value; }
            }
    
            /// <summary>
            /// 索引器
            /// </summary>
            /// <param name="index"></param>
            /// <returns></returns>
            public T this[int index]
            {
                get { return data[index]; }
                set { data[index] = value; }
            }
    
            /// <summary>
            /// 栈顶属性
            /// </summary>
            public int Top
            {
                get { return top; }
            }
    
            /// <summary>
            /// 初始化栈
            /// </summary>
            /// <param name="size"></param>
            public SeqStack(int size)
            {
                data = new T[size];
                maxsize = size;
                top = -1;
            }
    
            /// <summary>
            /// 清空顺序栈
            /// </summary>
            public void Clear()
            {
                top = -1;
            }
    
            /// <summary>
            /// 求栈的长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return top + 1;
            }
    
            /// <summary>
            /// 判断顺序栈是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if(top == -1)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 判断顺序栈是否已满
            /// </summary>
            /// <returns></returns>
            public bool IsFull()
            {
                if(top ==maxsize - 1)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 获取栈顶数据元素
            /// </summary>
            /// <returns></returns>
            public T GetTop()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Stack is empty");
                    return default(T);
                }else
                {
                    return data[top];
                }
            }
    
            /// <summary>
            /// 入栈操作
            /// </summary>
            /// <param name="item"></param>
            public void Push(T elem)
            {
                if(IsFull())
                {
                    Console.WriteLine("Stack is Full");
                }else
                {
                    //i++ 是后缀运算,就是 先返回 i 的值, i再 +1; 
                    //++i 是前缀运算, 就是 i先 + 1,再返回i 的值 ;
                    //i=1
                    //j = i++;  //j = 1, i = 2
                    //j = ++i;  //j = 2, i = 2
    
                    data[++top] = elem; //注意：这里是++top ,不是top++
                }
            }
    
            /// <summary>
            /// 出栈操作
            /// </summary>
            /// <returns></returns>
            public T Pop()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Stack is empty");
                    return default(T);
                }
    
                T temp = data[top];
                top--;
                return temp;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70]: /images/20210725/a3e32f0d71bb41ca9e229e287516926b.png