数据结构与算法（五）栈的顺序存储结构

这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战

栈是限定仅在表尾进行插入和删除操作的线性表。

我们将允许插入和删除的一端称为栈顶，另一端称为栈底。

不含任何元素的栈称为空栈。

栈又被称为先进后出的线性表。

也就是说栈是一个特殊的线性表，其只在线性表的表尾进行添加删除数据操作，也就是说上边提到的栈底是固定的，添加删除操作只在栈顶进行。

栈的写入操作，叫做进栈，也称压栈或入栈。

栈的删除操作，叫做出栈，也称弹出栈。

栈限定了只在线性表的末尾进行数据写入删除操作，但是这并不意味着最先进栈的元素一定要最后出栈，这个要看具体情况，举个书上的小例子

【进栈出栈的变化形式】

如果3个整数1,2,3依次入栈，会有哪些出栈次序？

第一种：1-2-3进栈，即3-2-1出栈。

第二种：1进，1出，2斤，2出，3进，3出，进一个出一个，即1-2-3出栈。

第三种：1进，2进，2出，1出，3进，3出，即2-1-3出栈。

第四种：1进，1出，2进，3进，3出，2出，即1-3-2出栈。

第五种：1进，2进，2出，3进，3出，2出，即2-3-1出栈

下边我们来定义栈顺序存储结构的接口：

csharp复制代码/// <summary>
    /// 栈接口
    /// </summary>
    /// <typeparam name="T"></typeparam>
    interface IStack<T>
    {
        /// <summary>
        /// 清空栈
        /// </summary>
        /// <returns></returns>
        bool ClearStack();
        /// <summary>
        /// 判断栈是否为空
        /// </summary>
        /// <returns>true:空、false：不空</returns>
        bool IsEmptyStack();
        /// <summary>
        /// 获取栈顶元素
        /// </summary>
        /// <returns></returns>
        T GetTopStack();
        /// <summary>
        /// 入栈
        /// </summary>
        /// <returns></returns>
        bool PushStack(T val);
        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        bool PopStack();
        /// <summary>
        /// 获取栈长度
        /// </summary>
        /// <returns></returns>
        int LengthStack();
        /// <summary>
        /// 判断栈是否已满
        /// </summary>
        /// <returns></returns>
        bool IsFull();
        /// <summary>
        /// 打印栈
        /// </summary>
        void paint();
    }

定义一个类来实现这个接口：

首先定义三个全局变量

csharp复制代码/// <summary>
        /// 顺序栈的容量（数组最大长度）
        /// </summary>
        private int maxsize;
        /// <summary>
        /// 数组，用于存储顺序栈中的数据元素
        /// </summary>
        private T[] data;
        /// <summary>
        /// 指示顺序栈的栈顶(top = -1 时表示栈为空)
        /// </summary>
        private int top;

这个和线性表（顺序存储结构）是一致的。

这里要说明一下顶栈top这个变量，当栈为空时，其为值-1，因此当想清空栈的时候，不需要将链表循环清空，只需将顶栈置为-1即可。

下方是我整个类的代码：具体调用的实例在文末，可下载：

csharp复制代码public class StackList<T> : IStack<T>
    {
        /// <summary>
        /// 顺序栈的容量（数组最大长度）
        /// </summary>
        private int maxsize;
        /// <summary>
        /// 数组，用于存储顺序栈中的数据元素
        /// </summary>
        private T[] data;
        /// <summary>
        /// 指示顺序栈的栈顶(top = -1 时表示栈为空)
        /// </summary>
        private int top;
        /// <summary>
        /// 构造函数
        /// </summary>
        public StackList(int size)
        {
            data = new T[size];
            maxsize = size;
            top = -1;
        }
        /// <summary>
        /// 清空栈(这里不需要将数组清空，只要将顶栈赋值为-1就好)
        /// </summary>
        /// <returns></returns>
        public bool ClearStack()
        {
            top = -1;
            return true;
        }
        /// <summary>
        /// 获取栈顶
        /// </summary>
        /// <returns></returns>
        public T GetTopStack()
        {
            T res = data[top];
            return res;
        }
        /// <summary>
        /// 是否是空栈
        /// </summary>
        /// <returns></returns>
        public bool IsEmptyStack()
        {
            if (top == -1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        /// <summary>
        /// 获取栈的长度
        /// </summary>
        /// <returns></returns>
        public int LengthStack()
        {
            return top + 1;
        }
        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        public bool PopStack()
        {
            if (IsEmptyStack())
            {
                Console.WriteLine("栈为空，无法删除！");
                return false;
            }
            T temp = default(T);
            data[top] = temp;
            top--;
            return true;
        }
        /// <summary>
        /// 入栈
        /// </summary>
        /// <returns></returns>
        public bool PushStack(T val)
        {
            if (IsFull())
            {
                Console.WriteLine("栈已满，写入失败！");
                return false;
            }
            top++;
            data[top] = val;
            return true;
        }
        /// <summary>
        /// 判断栈是否已满
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            if (top == maxsize - 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        /// <summary>
        /// 打印栈
        /// </summary>
        public void paint()
        {
            Console.WriteLine("栈顶："+top);
            for (int i = 0; i < data.Length; i++)
            {
                Console.WriteLine("index:"+i + " | data:"+data[i]);
            }
        }
    }