數據結構之隊列、棧是很常見的數據結構,那麼其使用場景是什麼呢?以及其區別是什麼,本文將通過簡單的實例來分表模擬其實際使用 ...
一、前言:
數據結構中隊列和棧也是常見的兩個數據結構,隊列和棧在實際使用場景上也是相輔相成的,下麵簡單總結一下,如有不對之處,多多指點交流,謝謝。
二、隊列簡介
隊列顧名思義就是排隊的意思,根據我們的實際生活不難理解,排隊就是有先後順序,先到先得,其實在程式數據結構中的隊列其效果也是一樣,及先進先出。
隊列大概有如下一些特性:
1、操作靈活,在初始化時不需要指定其長度,其長度自動增加(預設長度為32)
註:在實際使用中,如果事先能夠預估其長度,那麼在初始化時指定長度,可以提高效率
2、泛型的引入,隊列在定義時可以指定數據類型避免裝箱拆箱操作
3、存儲數據滿足先進先出原則
c#中有關隊列的幾個常用方法:
-
- Count:Count屬性返回隊列中元素個數。
- Enqueue:Enqueue()方法在隊列一端添加一個元素。
- Dequeue:Dequeue()方法在隊列的頭部讀取和刪除元素。如果在調用Dequeue()方法時,隊列中不再有元素,就拋出一個InvalidOperationException類型的異常。
- Peek:Peek()方法從隊列的頭部讀取一個元素,但不刪除它。
- TrimExcess:TrimExcess()方法重新設置隊列的容量。Dequeue()方法從隊列中刪除元素,但它不會重新設置隊列的容量。要從隊列的頭部去除空元素,應使用TrimExcess()方法。
- Clear:Clear()方法從隊列中移除所有的元素。
- ToArray:ToArray()複製隊列到一個新的數組中。
下麵通過隊列來實例模擬消息隊列的實現流程:
using System; using System.Collections; using System.Collections.Generic; namespace dataStructureQueueTest { class Program { static void Main(string[] args) { Console.WriteLine("通過Queue來模擬消息隊列的實現"); QueueTest queueTest = new QueueTest(); while (true) { Console.WriteLine("請輸入你操作的類型:1:代表生成一條消息,2:代表消費一條消息"); string type = Console.ReadLine(); if (type == "1") { Console.WriteLine("請輸入具體消息:"); string inforValue = Console.ReadLine(); queueTest.InformationProducer(inforValue); } else if (type == "2") { //// 在消費消息的時候,模擬一下,消費成功與消費失敗下次繼續消費的場景 object inforValue = queueTest.InformationConsumerGet(); if (inforValue == null) { Console.WriteLine("當前無可消息可消費"); } else { Console.WriteLine("獲取到的消息為:" + inforValue); Console.WriteLine("請輸入消息消費結果:1:成功消費消息,2:消息消費失敗"); string consumerState = Console.ReadLine(); ///// 備註:該操作方式線程不安全,在多線程不要直接使用 if (consumerState == "1") { queueTest.InformationConsumerDel(); } } } else { Console.WriteLine("操作有誤,請重新選擇"); } } } } /// <summary> /// 隊列練習 /// </summary> public class QueueTest { /// <summary> /// 定義一個隊列 /// </summary> public Queue<string> queue = new Queue<string>(); /// <summary> /// 生成消息--入隊列 /// </summary> /// <param name="inforValue"></param> public void InformationProducer(string inforValue) { queue.Enqueue(inforValue); } /// <summary> /// 消費消息---出隊列--只獲取數據,不刪除數據 /// </summary> /// <returns></returns> public object InformationConsumerGet() { if (queue.Count > 0) { return queue.Peek(); } return null; } /// <summary> /// 消費消息---出隊列---獲取數據的同時刪除數據 /// </summary> /// <returns></returns> public string InformationConsumerDel() { if (queue.Count > 0) { return queue.Dequeue(); } return null; } } }
三、棧簡介
棧和隊列在使用上很相似,只是棧的數據存儲滿足先進後出原則,棧有如下一些特性:
1、操作靈活,在初始化時不需要指定其長度,其長度自動增加(預設長度為10)
註:在實際使用中,如果事先能夠預估其長度,那麼在初始化時指定長度,可以提高效率
2、泛型的引入,棧在定義時可以指定數據類型避免裝箱拆箱操作
3、存儲數據滿足先進後出原則
c#中有關棧的幾個常用方法:
- Count:Count屬性返回棧中的元素個數。
- Push:Push()方法在棧頂添加一個元素。
- Pop:Pop()方法從棧頂刪除一個元素,並返回該元素。如果棧是空的,就拋出一個InvalidOperationException類型的異常。
- Peek:Peek()方法返回棧頂的元素,但不刪除它。
- Contains:Contains()方法確定某個元素是否在棧中,如果是,就返回true。
下麵通過一個棧來模擬瀏覽器的回退前進操作的實現
using System; using System.Collections.Generic; namespace dataStructureStackTest { class Program { static void Main(string[] args) { //// 通過棧來模擬瀏覽器回退前進操作 //// 1、定義兩個棧,分別記錄回退的地址集合,和前進地址集合 //// 2、在操作具體的回退或者前進操作時 //// 如果和前一次操作相同,那麼就取出對應隊列的一條數據存儲到另外一個隊列 Console.WriteLine("本練習模擬瀏覽器的回退前進操作:"); /// 假設瀏覽器已瀏覽了20個網站記錄 StackTest stackTestBack = new StackTest(20); StackTest stackTestGo = new StackTest(20); for (int i = 0; i < 20; i++) { stackTestBack.PushStack("網站" + (i + 1).ToString()); } //// 記錄上一次操作 string beforOpert = ""; while (true) { Console.WriteLine(""); Console.WriteLine("請輸入你操作的類型:1:回退,2:前進"); string type = Console.ReadLine(); if (type == "1") { //// 出棧 if (beforOpert == type) { stackTestGo.PushStack(stackTestBack.GetAndDelStack()); } string wbeSit = stackTestBack.GetStack(); Console.WriteLine("回退到頁面:" + wbeSit); beforOpert = type; } else if (type == "2") { //// 出棧 if (beforOpert == type) { stackTestBack.PushStack(stackTestGo.GetAndDelStack()); } string wbeSit = stackTestGo.GetStack(); Console.WriteLine("回退到頁面:" + wbeSit); beforOpert = type; } else { Console.WriteLine("請輸入正確的操作方式!!"); } } } } /// <summary> /// 隊列練習 /// </summary> public class StackTest { /// <summary> /// 定義一個棧 /// </summary> public Stack<string> stack; /// <summary> ///無參數構造函數,棧初始化為預設長度 /// </summary> public StackTest() { stack = new Stack<string>(); } /// <summary> ///有參數構造函數,棧初始化為指定長度 ///如果在定義隊列時,如果知道需要存儲的數據長度,那麼最好預估一個長度,並初始化指定的長度 /// </summary> public StackTest(int stackLen) { stack = stackLen > 0 ? new Stack<string>(stackLen) : new Stack<string>(); } /// <summary> /// 入棧 /// </summary> /// <param name="inforValue"></param> public void PushStack(string inforValue) { stack.Push(inforValue); } /// <summary> /// 出棧(但不刪除) /// </summary> /// <returns></returns> public string GetStack() { if (stack.Count > 0) { return stack.Peek(); } return null; } /// <summary> /// 出棧(並刪除) /// </summary> /// <returns></returns> public string GetAndDelStack() { if (stack.Count > 0) { return stack.Pop(); } return null; } } }
四、使用場景總結
根據隊列和棧的特點,下麵簡單總結一下隊列和棧的一些實際使用場景
隊列:
1、非同步記錄日誌,此處會涉及到單例模式的使用
2、消息隊列
3、業務排隊,比如12306車票購買排隊等候
4、其他符合先進先出原則的業務操作
棧:
1、可回退的操作記錄,比如:瀏覽器的回退操作
2、計算表達式匹配,比如:計算器表達式計算
3、其他符合先進後出原則的業務操作
附件:
關於這一些練習的代碼,上傳到github,有興趣的可以看一下:
https://github.com/xuyuanhong0902/dataStructureTest.git