實現一個雙端隊列的步驟簡析
01 故事起源
隊列是一種先進先出的數據結構。 
?
一般通過數組實現。
?
還需要定義2個指針，頭指針和尾指針。 
?
02 插入和刪除
2.1 插入
從隊尾tail處插入，再將tail指針后移。 
2.2 刪除
從隊首head處取出元素，再將head指針后移。 
?
但數組是定長的，如果多次插入刪除，tail指針就會超出數組范圍，而前面其實還是有空間的，所以常用的還是循環隊列。 
?
03 循環隊列
循環其實就是讓head,tail兩個指針在數組內循環移動，當移動到隊尾時就跳到隊首。 
?
通過取模就可以實現循環。 
?
當head==tail時，即為隊空。
?
當head==(tail+1)%n時，即為隊滿。如果隊列長度為n，則只能裝n-1個元素，最后一個元素要空著。因為如果放入元素，tail會和head重合，就無法判斷是隊空還是隊滿。
? ?
04 雙端隊列
普通隊列只能隊首出，隊尾進，但有時我們需要隊首和隊尾都能進出，即雙端隊列。 
4.1 插入
隊首插入，則head指針前移；隊尾插入，則tail指針后移。 
4.2 刪除
隊首刪除，則head指針后移；隊尾刪除，則tail指針前移。
?
05 代碼實現
實現一個模板，以后可重復利用。
先定義必要的方法和變量。
構造函數
插入
刪除
size方法
使用案例
06 總結
隊列是非常基礎且重要的數據結構，雙端隊列屬于隊列的升級。很多的算法都是基于隊列來實現，例如搜索中的bfs，圖論中的spfa，計算幾何中的melkman等。隊列結構本身很簡單，如何使用才是比較難的，一定要深刻理解，以后才能熟練應用到不同的模型中。
審核編輯：劉清
聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容侵權或者其他違規問題，請聯系本站處理。
舉報投訴
-
BFS
+關注
關注
0文章
9瀏覽量
2188
原文標題：如何實現一個雙端隊列？
文章出處：【微信號：TheAlgorithm，微信公眾號：算法與數據結構】歡迎添加關注！文章轉載請注明出處。
發布評論請先 登錄
相關推薦
【設計技巧】rtos的核心原理簡析
rtos的核心原理簡析rtos全稱real-time operating system（實時操作系統），我來簡單分析下：我們都知道，c語句中調用一個函數后，該函數的返回地址都是放在堆棧
發表于 07-23 08:00
Rockchip RK3399 Linux4.4 USB DTS配置步驟簡析
1、Rockchip RK3399 Linux4.4 USB DTS配置步驟簡析本文檔提供RK3399 USB DTS的配置方法。RK3399支持兩個Type-C USB3.0(Typ
發表于 08-10 16:10
簡析BGA封裝技術與質量控制
簡析BGA封裝技術與質量控制
ＳＭＴ（Surface Mount Technology)表面安裝技術順應了電子產品小型化、輕型化的潮流趨勢，為實現電子
發表于 03-30 16:49
?1511次閱讀
簡析用電阻設定增益的單端至差分轉換器資料下載
電子發燒友網為你提供簡析用電阻設定增益的單端至差分轉換器資料下載的電子資料下載，更有其他相關的電路圖、源代碼、課件教程、中文資料、英文資料、參考設計、用戶指南、解決方案等資料，希望可以幫助到廣大的電子工程師們。
發表于 04-04 08:46
?3次下載
TencentOS-tiny中環形隊列的實現
1. 什么是隊列隊列（queue）是一種只能在一端插入元素、在另一端刪除元素的數據結構，遵循「先入先出」（FIFO）的規則。 隊列中有兩
利用C++提供的隊列封裝一個消息隊列
最近的C++項目中，需要用到消息隊列，但是C++中又沒有原生的消息隊列，就在網上找了一下相關資料，利用C++提供的隊列，自己封裝一
巖土工程監測中振弦采集儀的布設方案及實施步驟簡析
巖土工程監測中振弦采集儀的布設方案及實施步驟簡析 巖土工程監測中，河北穩控科技振弦采集儀是一種常用的地下水位和土層壓縮性監測工具。它通過采集振弦的振動信號來確定地下水位和土層的壓縮性，
工商網監
評論