重生之数据结构与算法----队列&栈

1A9wq7NjN

简介

上文说到，数据结构只有两种。其它的数据结构都是它的整花活。

• 栈
  栈只能在表的一端（称为栈顶）进行插入和删除操作，遵循 “后进先出”（Last In First Out，LIFO）的原则。就像生活中的一摞盘子，最后放上去的盘子会最先被拿走
  
• 队列
  它只允许在表的一端进行插入操作（队尾），在另一端进行删除操作（队头），遵循 “先进先出”（First In First Out，FIFO）的原则。类似于生活中排队买票，先排队的人先买到票离开队列。
  

用链表实现stack

    public class MyLinkedStack<T>()    {        public static void Run()        {            var stack = new MyLinkedStack<string>();            stack.Push("aaaa");            stack.Push("bbbb");            stack.Push("cccc");            stack.Push("dddd");            while (stack.Count > 0)            {                Console.WriteLine(stack.Pop());            }                    }        private LinkedList<T> _linked = new LinkedList<T>();        /// <summary>        /// 入栈        /// O(1)        /// </summary>        /// <param name="item"></param>        public void Push(T item)        {            _linked.AddFirst(item);        }        /// <summary>        /// 出栈        /// O(1)        /// </summary>        /// <returns></returns>        public T Pop()        {            var first = _linked.First;            _linked.RemoveFirst();            return first.Value;        }        /// <summary>        /// 查看栈顶        /// </summary>        /// O(1)        /// <returns></returns>        public T Peek()        {            return _linked.First.Value;        }        public int Count { get { return _linked.Count; } }    }用链表实现queue

public class MyLinkedQueue<T>{    public static void Run()    {        var queue = new MyLinkedQueue<string>();        queue.Enqueue("aaa");        queue.Enqueue("bbb");        queue.Enqueue("ccc");        queue.Enqueue("ddd");        while (queue.Count > 0)        {            Console.WriteLine(queue.Dequeue());        }    }    private LinkedList<T> _linked = new LinkedList<T>();    /// <summary>    /// 入列    /// </summary>    /// <param name="item"></param>    public void Enqueue(T item)    {        _linked.AddFirst(item);    }    /// <summary>    /// 出列    /// </summary>    /// <returns></returns>    public T Dequeue()    {        var last= _linked.Last;        _linked.RemoveLast();        return last.Value;    }    /// <summary>    /// 查看队列顶    /// </summary>    /// <returns></returns>    public T Peek()    {        return _linked.First.Value;    }    public int Count { get { return _linked.Count; } }}用数组实现stack

    public class MyArrayStack<T>()    {        public static void Run()        {            var stack = new MyLinkedStack<string>();            stack.Push("aaaa");            stack.Push("bbbb");            stack.Push("cccc");            stack.Push("dddd");            while (stack.Count > 0)            {                Console.WriteLine(stack.Pop());            }        }        private List<T> _list=new List<T>();        /// <summary>        /// 入栈        /// O(1)        /// </summary>        /// <param name="item"></param>        public void Push(T item)        {            _list.Add(item);        }        /// <summary>        /// 出栈        /// O(1)        /// </summary>        /// <returns></returns>        public T Pop()        {            var v = _list[_list.Count - 1];            _list.RemoveAt(_list.Count - 1);            return v;        }        /// <summary>        /// 查看栈顶        /// </summary>        /// O(1)        /// <returns></returns>        public T Peek()        {            return _list[_list.Count - 1];        }        public int Count { get { return _list.Count; } }    }用数组实现queue

由于queue先进先出的特性，list头部增删元素的复杂度是O(N),不符合性能要求，我们可以使用前文介绍的环形数组，来实现list头部增删的O(1)
public class MyArrayQueue<T>{    public static void Run()    {        var queue = new MyArrayQueue<string>();        queue.Push("aaaa");        queue.Push("bbbb");        queue.Push("cccc");        queue.Push("dddd");        while (queue.Count > 0)        {            Console.WriteLine(queue.Pop());        }    }    private CircularArray<T> _list = new CircularArray<T>();    /// <summary>    /// 入栈    /// O(1)    /// </summary>    /// <param name="item"></param>    public void Push(T item)    {        _list.AddFirst(item);    }    /// <summary>    /// 出栈    /// O(1)    /// </summary>    /// <returns></returns>    public T Pop()    {        var v = _list.GetLast();        _list.RemoveLast();        return v;    }    /// <summary>    /// 查看栈顶    /// </summary>    /// O(1)    /// <returns></returns>    public T Peek()    {        return _list.GetFirst();    }    public int Count { get { return _list.Count; } }}队列的变种：双端队列

所谓双端队列，主要是比普通队列，多一个出入口,可以从队列的两头进行插入，删除。但也破坏了先进先出的原则。
日常场景使用不多。只有 Python用得多一些，因为Python标准库没有提供内置的栈和队列，一般会用双端队列来模拟标准队列。
    public interface IMyQueue<T>    {        /// <summary>        /// 从头入列        /// </summary>        /// <param name="item"></param>        void EnqueueFirst(T item);        /// <summary>        /// 从头出列        /// </summary>        /// <param name="item"></param>        /// <returns></returns>        T DequeueFirst(T item);        /// <summary>        /// 从尾入列        /// </summary>        void EnqueueLast();        /// <summary>        /// 从头出列        /// </summary>        /// <returns></returns>        T DequeueLast();    }

实现比较简单，不再重复，参考普通队列思路即可。链表/环形数组均可实现。