重生之数据结构与算法----队列&栈
简介上文说到，数据结构只有两种。其它的数据结构都是它的整花活。
[*]栈
栈只能在表的一端（称为栈顶）进行插入和删除操作，遵循 “后进先出”（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.RemoveAt(_list.Count - 1); return v; } /// <summary> /// 查看栈顶 /// </summary> /// O(1) /// <returns></returns> public T Peek() { return _list; } 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(); }实现比较简单，不再重复，参考普通队列思路即可。链表/环形数组均可实现。
页:
[1]