欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C#底层模拟实现Stack数组栈,栈的先进后出。

程序员文章站 2024-03-18 18:07:16
...

对于栈,普通用户只需要能够获取栈的元素数量,是否为空,增删查,就可以了,所以我们定义一个规范。*====接口*
定义一个泛型接口IStack

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 数组栈
{
    interface IStack<E>
    {
        //栈中元素数量
         int Count { get;  }

        //是否为空
        bool IsEmpty { get; }

        //添加
        void Push(E e);

        //删除
        E Pop();

        //查找
        E Peek();
    }
}

定义一个类Array1Stack去实现接口

using ClassLibrary1;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;





namespace 数组栈
{
    class Array1Stack<E> : IStack<E>
    {


        private Array1<E> arr;


        //自定义容量
        public Array1Stack(int capacity)
        {
            arr = new Array1<E>(capacity);
        }

        //默认
        public Array1Stack()
        {
            arr = new Array1<E>();
        }

        public int Count { get { return arr.Count; }}

        public bool IsEmpty { get { return arr.IsEmpty; } }

        //查询
        public E Peek()
        {
            return arr.GetLast();
        }

        //删除
        public E Pop()
        {
            return arr.RemoveLast();
        }

        //添加元素
        public void Push(E e)
        {
            //向尾部添加     时间复杂度知  尾部添加为O(1)
            arr.AddLast(e);
        }

        public override string ToString()
        {
            return "Stack:" + arr.ToString() + "top";
        }
    }
}

动态数组的底层实现,之前文章有具体介绍,这里我们直接拿来用。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ClassLibrary1
{
   public class Array1<E>
    {
        private E[] Data;
        private int N; //存在的元素个数
        /// <summary>
        /// 初始化构造函数   
        /// </summary>
        /// <param name="capacity">初始化内存</param>
        public Array1(int capacity)
        {
            Data = new E[capacity];
            N = 0;
        }

        //默认10个容量
        public Array1() : this(10)
        {

        }

        //数组长度
        public int Capacity
        {
            get { return Data.Length; }
        }

        //存储元素的多少
        public int Count
        {
            get { return N; }
        }

        //判断动态数组是否为空
        public bool IsEmpty
        {
            get { return N == 0; }
        }


        //添加元素
        public void Add(int index, E e)
        {
            if (index < 0 || index > N)
            {
                throw new ArgumentException("数组索引越界");
            }
            if (N == Data.Length)
            {   //扩容
                ResetCapacity(2 * Data.Length);
            }

            for (int i = N - 1; i >= index; i--)
            {
                Data[i + 1] = Data[i];
            }

            Data[index] = e;
            N++;


        }

        //向尾部添加
        public void AddLast(E e)
        {
            Add(N, e);
        }
        //向头添加
        public void AddFirst(E e)
        {
            Add(0, e);
        }

        //获指定索引元素
        public E Get(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("数组索引越界");
            }
            return Data[index];
        }

        /// <summary>
        /// 获取数组中的第一个元素
        /// </summary>
        /// <returns></returns>
        public E GetFirst()
        {
            return Get(0);
        }

        /// <summary>
        /// 获取最后一个元素
        /// </summary>
        /// <returns></returns>
        public E GetLast()
        {
            return Get(N - 1);
        }


        /// <summary>
        /// 修改指定下标赋值
        /// </summary>
        /// <param name="index">下标</param>
        /// <param name="newE">值</param>
        public void Set(int index, E newE)
        {
            if (index < 0 || index >= N)
            {
                throw new ArgumentException("数组索引越界");
            }
            Data[index] = newE;
        }

        /// <summary>
        /// 查看元素是否存在
        /// </summary>
        /// <param name="e"></param>
        /// <returns></returns>
        public bool Contains(int e)
        {
            for (int i = 0; i < N; i++)
            {
                if (Data[i].Equals(e))
                {
                    return true;
                }
            }
            return false;

        }


        /// <summary>
        /// 返回元素位置
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int IndexOf(int n)
        {
            for (int i = 0; i < N; i++)
            {
                if (Data[i].Equals(n))
                {
                    return i;
                }
            }
            return -1;
        }


        /// <summary>
        /// 删除指定位置元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public E RemoveAt(int index)
        {

            if (index < 0 || index >= N)
            {
                throw new ArgumentException("索引超出了数组界限");
            }
            E del = Data[index];
            for (int i = index + 1; i <= N - 1; i++)
            {
                Data[i - 1] = Data[i];
            }
            N--;
            Data[N] = default(E);  //引用类型会赋值为空   值类型会赋值为0

            //缩容操作  当元素个数等于容量的四分之一的时候就进行缩容操作
            if (N == Data.Length / 4)
                ResetCapacity(Data.Length / 2);

            return del;
        }


        public E RemoveFirst()
        {
            return RemoveAt(0);
        }


        public E RemoveLast()
        {
            return RemoveAt(N - 1);
        }

        //删除指定元素
        public void Remove(int e)
        {
            int index = IndexOf(e);
            if (index != -1)
                RemoveAt(index);
        }

        /// <summary>
        /// 容量扩容
        /// </summary>
        /// <param name="newCapacity"></param>
        private void ResetCapacity(int newCapacity)
        {
            E[] newDate = new E[newCapacity];
            for (int i = 0; i < N; i++)
            {
                newDate[i] = Data[i];
            }
            Data = newDate;
        }



        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            //res.Append(string.Format("Array1: count={0} capacity={1}\n", N, Data.Length));
            res.Append("[");
            for (int i = 0; i < N; i++)
            {
                res.Append(Data[i]);
                if (i != N - 1)
                {
                    res.Append(", ");
                }

            }
            res.Append("]");
            return res.ToString();
        }

    }
}

这样我们就通过动态数组快速搭建了一个栈。

Main方法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console; 

namespace 数组栈
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1Stack<int> stack = new Array1Stack<int>();
            //进栈
            for (int i = 0; i < 5; i++)
            {
                stack.Push(i);
                WriteLine(stack);
            }
            //出栈
            for (int i = 0; i < 5; i++)
            {
                stack.Pop();
                WriteLine(stack);
            }



            Read();
        }
    }
}

结果:
C#底层模拟实现Stack数组栈,栈的先进后出。

相关标签: 数据结构 C#