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

简介

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

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

用链表实现stack

1.     public class MyLinkedStack<T>()
2.     {
3.         public static void Run()
4.         {
5.             var stack = new MyLinkedStack<string>();
7.             stack.Push("aaaa");
8.             stack.Push("bbbb");
9.             stack.Push("cccc");
10.             stack.Push("dddd");
12.             while (stack.Count > 0)
13.             {
14.                 Console.WriteLine(stack.Pop());
15.             }
16.             
17.         }
18.         private LinkedList<T> _linked = new LinkedList<T>();
20.         /// <summary>
21.         /// 入栈
22.         /// O(1)
23.         /// </summary>
24.         /// <param name="item"></param>
25.         public void Push(T item)
26.         {
27.             _linked.AddFirst(item);
28.         }
30.         /// <summary>
31.         /// 出栈
32.         /// O(1)
33.         /// </summary>
34.         /// <returns></returns>
35.         public T Pop()
36.         {
37.             var first = _linked.First;
38.             _linked.RemoveFirst();
39.             return first.Value;
40.         }
41.         /// <summary>
42.         /// 查看栈顶
43.         /// </summary>
44.         /// O(1)
45.         /// <returns></returns>
46.         public T Peek()
47.         {
48.             return _linked.First.Value;
49.         }
51.         public int Count { get { return _linked.Count; } }
52.     }

复制代码

用链表实现queue

1. public class MyLinkedQueue<T>
2. {
3.     public static void Run()
4.     {
5.         var queue = new MyLinkedQueue<string>();
8.         queue.Enqueue("aaa");
9.         queue.Enqueue("bbb");
10.         queue.Enqueue("ccc");
11.         queue.Enqueue("ddd");
13.         while (queue.Count > 0)
14.         {
15.             Console.WriteLine(queue.Dequeue());
16.         }
17.     }
19.     private LinkedList<T> _linked = new LinkedList<T>();
21.     /// <summary>
22.     /// 入列
23.     /// </summary>
24.     /// <param name="item"></param>
25.     public void Enqueue(T item)
26.     {
27.         _linked.AddFirst(item);
28.     }
30.     /// <summary>
31.     /// 出列
32.     /// </summary>
33.     /// <returns></returns>
34.     public T Dequeue()
35.     {
36.         var last= _linked.Last;
37.         _linked.RemoveLast();
38.         return last.Value;
39.     }
41.     /// <summary>
42.     /// 查看队列顶
43.     /// </summary>
44.     /// <returns></returns>
45.     public T Peek()
46.     {
47.         return _linked.First.Value;
48.     }
50.     public int Count { get { return _linked.Count; } }
51. }

复制代码

用数组实现stack

1.     public class MyArrayStack<T>()
2.     {
3.         public static void Run()
4.         {
5.             var stack = new MyLinkedStack<string>();
7.             stack.Push("aaaa");
8.             stack.Push("bbbb");
9.             stack.Push("cccc");
10.             stack.Push("dddd");
12.             while (stack.Count > 0)
13.             {
14.                 Console.WriteLine(stack.Pop());
15.             }
17.         }
18.         private List<T> _list=new List<T>();
20.         /// <summary>
21.         /// 入栈
22.         /// O(1)
23.         /// </summary>
24.         /// <param name="item"></param>
25.         public void Push(T item)
26.         {
27.             _list.Add(item);
28.         }
30.         /// <summary>
31.         /// 出栈
32.         /// O(1)
33.         /// </summary>
34.         /// <returns></returns>
35.         public T Pop()
36.         {
37.             var v = _list[_list.Count - 1];
38.             _list.RemoveAt(_list.Count - 1);
39.             return v;
40.         }
42.         /// <summary>
43.         /// 查看栈顶
44.         /// </summary>
45.         /// O(1)
46.         /// <returns></returns>
47.         public T Peek()
48.         {
49.             return _list[_list.Count - 1];
50.         }
52.         public int Count { get { return _list.Count; } }
53.     }

复制代码

用数组实现queue

由于queue先进先出的特性，list头部增删元素的复杂度是O(N),不符合性能要求，我们可以使用前文介绍的环形数组，来实现list头部增删的O(1)

1. public class MyArrayQueue<T>
2. {
3.     public static void Run()
4.     {
5.         var queue = new MyArrayQueue<string>();
7.         queue.Push("aaaa");
8.         queue.Push("bbbb");
9.         queue.Push("cccc");
10.         queue.Push("dddd");
12.         while (queue.Count > 0)
13.         {
14.             Console.WriteLine(queue.Pop());
15.         }
17.     }
18.     private CircularArray<T> _list = new CircularArray<T>();
20.     /// <summary>
21.     /// 入栈
22.     /// O(1)
23.     /// </summary>
24.     /// <param name="item"></param>
25.     public void Push(T item)
26.     {
27.         _list.AddFirst(item);
28.     }
30.     /// <summary>
31.     /// 出栈
32.     /// O(1)
33.     /// </summary>
34.     /// <returns></returns>
35.     public T Pop()
36.     {
37.         var v = _list.GetLast();
38.         _list.RemoveLast();
39.         return v;
40.     }
42.     /// <summary>
43.     /// 查看栈顶
44.     /// </summary>
45.     /// O(1)
46.     /// <returns></returns>
47.     public T Peek()
48.     {
49.         return _list.GetFirst();
50.     }
52.     public int Count { get { return _list.Count; } }
53. }

复制代码

队列的变种：双端队列

所谓双端队列，主要是比普通队列，多一个出入口,可以从队列的两头进行插入，删除。但也破坏了先进先出的原则。
日常场景使用不多。只有 Python用得多一些，因为Python标准库没有提供内置的栈和队列，一般会用双端队列来模拟标准队列。

1.     public interface IMyQueue<T>
2.     {
3.         /// <summary>
4.         /// 从头入列
5.         /// </summary>
6.         /// <param name="item"></param>
7.         void EnqueueFirst(T item);
8.         /// <summary>
9.         /// 从头出列
10.         /// </summary>
11.         /// <param name="item"></param>
12.         /// <returns></returns>
13.         T DequeueFirst(T item);
14.         /// <summary>
15.         /// 从尾入列
16.         /// </summary>
17.         void EnqueueLast();
18.         /// <summary>
19.         /// 从头出列
20.         /// </summary>
21.         /// <returns></returns>
22.         T DequeueLast();
24.     }

复制代码

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！