跳到主要內容

用隊列實現棧，用棧實現隊列，聽起來有點繞，都搞懂了就掌握了精髓！

目錄

  • 一、背景

  • 二、概念

    • 2.1 棧

    • 2.2 隊列


  • 三、棧和隊列的相互實現

    • 3.1 用隊列實現棧

    • 3.2 用棧實現隊列


  • 四、總結



一、背景


棧和隊列是數據結構中最常用到的兩種結構，有非常廣泛的運用，該篇文章將通過動畫的手段，展示棧和隊列相互實現的底層原理，讓我們真正搞懂棧和隊列的特性。


二、概念


2.1 棧


棧[Stack]:是一種限定僅在表尾進行插入和刪除操作的線性表；即後進先出（LIFO-last in first out），最後插入的元素最先出來




  • 入棧（push）

  • 出棧 (pop)


2.2 隊列


　隊列[Queue]：是一種限定僅在表頭進行刪除操作，僅在表尾進行插入操作的線性表；即先進先出（FIFO-first in first out）:最先插入的元素最先出來。




  • 入隊(enqueue)


  • 出隊(dequeue)


三、棧和隊列的相互實現


3.1 用隊列實現棧


  • 模擬入棧的實現原理
    -- 棧的特性是新加入的元素出現在棧頂，保證後進先出。
    -- 隊列的特性為新加入的元素出現在隊尾，隊列的隊尾元素最後出隊。
    -- 按以上兩個前提，我們可以讓隊頭至隊尾前的其它所有元素依次出隊再入隊，直至在隊尾新加入的元素被移到隊頭，也即實現了讓新壓入的元素保留在棧頂。


  • 模擬出棧的實現原理
    -- 由於在入棧時保證隊列中新加入隊尾的元素被移到了隊頭，出棧只需彈出隊頭元素即可。


  • 完整代碼實現



/**
  * 用隊列模擬實現棧
  *
  * @author zhuhuix
  * @date 2020-06-09
  */
 public class QueueImplStack {
 
     // 定義隊列
     private Queue<Integer> queue;
 
     public QueueImplStack() {
         queue = new LinkedList();
     }
 
     // 入棧--在隊尾加入元素后,讓其他元素按順序出隊再入隊，保持新加入的元素永遠在隊頭
     public void push(Integer e) {
         queue.offer(e);
         int size = queue.size();
         int i = 0;
         while (i < size - 1) {
             queue.offer(queue.poll());
             i++;
         }
     }
 
     // 出棧--將隊尾前的其它所有元素出隊再入隊，直至隊尾元素移到隊頭
     public Integer pop() {
         return queue.poll();
     }
 
     // 查看棧頂元素--即隊頭元素
     public Integer peek() {
         return queue.peek();
     }
 
     // 是否為空
     public boolean isEmpty() {
         return queue.isEmpty();
     }
 
     public static void main(String[] args) {
         QueueImplStack stack = new QueueImplStack();
         stack.push(1);
         System.out.println(stack.peek());
         stack.push(2);
         System.out.println(stack.peek());
         stack.push(3);
         System.out.println(stack.peek());
         System.out.println("=============");
         System.out.println(stack.pop());
         System.out.println(stack.pop());
         System.out.println(stack.pop());
         System.out.println(stack.isEmpty());
 
     }
 }

3.2 用棧實現隊列


  • 模擬入隊的實現原理
    -- 隊列的特性最新入隊的元素需排在隊尾，最先入隊的元素排在隊頭，按隊頭到隊尾的順序依次出隊。
    -- 對應到棧的數據結構上，也即需將新加入的元素保留在棧頂，保證先進先出。
    -- 按以上兩個前提，需在存放數據的棧的基礎上再增加一個輔助棧，在每次入隊時，先將存放數據的棧彈入輔助棧，再把需加入的新元素壓入數據棧底，最後把輔助棧中的元素彈出依次壓入數據棧，這樣保證了新加入的元素，沉在棧底。

    - 模擬出隊的實現原理
    -- 由於在入隊時，通過數據棧與輔助棧的交換，實現了后加入的元素沉在棧底，先進入的元素保留在棧頂，直接通過出棧彈出即可。

    • 完整代碼實現



/**
  * 用棧模擬實現隊列
  *
  * @author zhuhuix
  * @date 2020-06-09
  */
 public class StackImplQueue {
     // 數據棧
     private Stack<Integer> stack;
     // 輔助棧
     private Stack<Integer> aux;
 
     StackImplQueue() {
         stack = new Stack<>();
         aux = new Stack<>();
     }
 
     // 入隊--通過數據棧與輔助棧相互交換，保證新加入的元素沉在數據棧底
     public void enqueue(Integer e) {
         while (!stack.isEmpty()) {
             aux.push(stack.pop());
         }
         stack.push(e);
         while(!aux.isEmpty()){
             stack.push(aux.pop());
         }
 
     }
 
     // 出隊--彈出數據棧元素
     public Integer dequeue(){
         return stack.pop();
     }
 
     // 查看隊頭元素
     public Integer peek(){
         return stack.peek();
     }
 
     // 是否為空
     public boolean isEmpty(){
         return stack.isEmpty();
     }
 
     public static void main(String[] args) {
         StackImplQueue queue = new StackImplQueue();
         queue.enqueue(1);
         System.out.println(queue.peek());
         queue.enqueue(2);
         System.out.println(queue.peek());
         queue.enqueue(3);
         System.out.println(queue.peek());
         System.out.println("=============");
         System.out.println(queue.dequeue());
         System.out.println(queue.dequeue());
         System.out.println(queue.dequeue());
 
     }
 }

四、總結


通過以上棧和隊列相互交叉的實踐，我們對棧和隊列的重大特性有了深入了解：



  • 棧和隊列都是線性連續結構，增加和刪除元素不會影響破此連續性

  • 棧通過棧頂的操作實現元素的增加與刪除，也即只能在一端進行操作

  • 隊列通過隊尾增加元素，隊頭刪除元素，也即可以在兩端操作

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】



※為什麼 USB CONNECTOR 是電子產業重要的元件?



※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!



※台北網頁設計公司全省服務真心推薦



※想知道最厲害的網頁設計公司"嚨底家"!



※推薦評價好的iphone維修中心



※網頁設計最專業,超強功能平台可客製化



※別再煩惱如何寫文案,掌握八大原則!


Orignal From: 用隊列實現棧，用棧實現隊列，聽起來有點繞，都搞懂了就掌握了精髓！

留言

張貼留言

這個網誌中的熱門文章

有了四步解題法模板，再也不害怕動態規劃！（看不懂算我輸）

導言 動態規劃問題一直是算法面試當中的重點和難點，並且動態規劃這種通過空間換取時間的算法思想在實際的工作中也會被頻繁用到，這篇文章的目的主要是解釋清楚 什麼是動態規劃 ，還有就是面對一道動態規劃問題，一般的 思考步驟 以及其中的注意事項等等，最後通過幾道題目將理論和實踐結合。 什麼是動態規劃 如果你還沒有聽說過動態規劃，或者僅僅只有耳聞，或許你可以看看 Quora 上面的這個 回答 。 How to explain dynamic 用一句話解釋動態規劃就是 " 記住你之前做過的事 "，如果更準確些，其實是 " 記住你之前得到的答案 "。 我舉個大家工作中經常遇到的例子。 在軟件開發中，大家經常會遇到一些系統配置的問題，配置不對，系統就會報錯，這個時候一般都會去 Google 或者是查閱相關的文檔，花了一定的時間將配置修改好。 過了一段時間，去到另一個系統，遇到類似的問題，這個時候已經記不清之前修改過的配置文件長什麼樣，這個時候有兩種方案，一種方案還是去 Google 或者查閱文檔，另一種方案是借鑒之前修改過的配置，第一種做法其實是萬金油，因為你遇到的任何問題其實都可以去 Google，去查閱相關文件找答案，但是這會花費一定的時間，相比之下，第二種方案肯定會更加地節約時間，但是這個方案是有條件的，條件如下： 之前的問題和當前的問題有着關聯性，換句話說，之前問題得到的答案可以幫助解決當前問題 需要記錄之前問題的答案 當然在這個例子中，可以看到的是，上面這兩個條件均滿足，大可去到之前配置過的文件中，將配置拷貝過來，然後做些細微的調整即可解決當前問題，節約了大量的時間。 不知道你是否從這些描述中發現，對於一個動態規劃問題，我們只需要從兩個方面考慮，那就是 找出問題之間的聯繫 ，以及 記錄答案 ，這裏的難點其實是找出問題之間的聯繫，記錄答案只是順帶的事情，利用一些簡單的數據結構就可以做到。 概念 上面的解釋如果大家可以理解的話，接    動態規劃 算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。它的幾個重要概念如下所述。    階段： 對於一個完整的問題過程，適當的切分為若干個相互聯繫的子問題，每次在求解一個子問題...
張貼留言
閱讀完整內容

計算機本地文件快要滅絕了

　　 編者按： 文件是数字世界的基石，是我們基本的工作單位。但是，隨着互聯網的雲化、平台化、服務化，文件日益變得可有可無。這樣一種改變究竟好不好呢？喜歡懷舊的 Simon Pitt 開始回顧各種文件的好處，哪怕這讓他顯得不合時宜。原文發表在 medium 上，標題是：Computer Files Are Going Extinct 　　我喜歡文件。我喜歡對文件重命名、移動、排序，改變它們在文件夾中的显示方式，去備份文件，將之上傳到互聯網，恢復它們，對其進行複製，甚至還可以對文件進行碎片整理。作為信息存儲方式的一種隱喻，在我看來文件是很出色的。我喜歡把文件當作一個工作單位。如果我要寫篇文章，文章會放在文件裏面。如果我要生成圖像，圖像會保存進文件裏面。 　　 謳歌 files.doc 　　文件是擬物化的。這是個很花哨的詞，只是用來表示文件是反映現實物品的一個数字概念。比方說，Word 文檔就像一張紙，躺在你的辦公桌上（desktop）。JPEG 就像一幅畫，等等。它們每個都有一個小圖標，圖標的樣子看起來像它們所代表的現實物品。一堆紙，一個畫框，一個馬尼拉文件夾。真的挺很迷人的。 　　我喜歡文件的一點是，不管裏面有什麼，跟文件的交互方式總是一致的。我上面提到的那些東西——複製、排序、碎片整理——我可以對任何文件進行那些處理。文件可能是圖像、遊戲的一部分、也可能是我最喜歡的餐具清單。碎片整理程序不在乎它是什麼。它不會去判斷內容。 　　自從我開始在 Windows 95 裏面創建文件以來，我就一直都很喜歡文件。但是我注意到我們已經開始慢慢地遠離把文件當作基本工作單位的做法。 Windows95。我的計算機 　　 services.mp3 的興起 　　十幾歲的時候，我開始痴迷於收集和管理数字音樂：我收藏 MP3 文件。一大堆的 128 kbps MP3 文件。如果你足夠幸運，有自己的 CD 刻錄機的話，就可以將它們刻錄到 CD 上，然後在朋友之間傳遞。一張 CD 可以容納 700 MB。這相當於將近 500 張軟盤！ 　　我會仔細端詳我的收藏，然後煞費苦心地給它們添加上 IDv1 和 IDv2 音樂標籤。隨着時間的流逝，大家開始開發可以在雲端自動獲取曲目列表的工具，這樣你就可以檢查和驗證 MP3 的質量。有時候我甚至會去聽那些該死的東西，儘管...
張貼留言
閱讀完整內容

純電動 Mini Cooper SE 將成為中國國產車，年產 16 萬輛

BMW 集團與中國長城汽車合資，將於江蘇建立新廠，專門投入生產 MINI Cooper SE 和部分長城品牌電動車，預計於 2022 年完工並投入生產，每年將可生產 16 萬輛電動車。 靈動可愛的 Mini Cooper，在許多車迷心中都有著特殊的地位，今年 7 月發表了首款純電動版本的 Mini Cooper SE 之後，獲得熱烈迴響，預訂數量已接近 8 萬台，顯示大家對於純電 Mini 的熱愛，因為油電版的 Mini Cooper Countryman 的全球總銷售量也才 3 萬出頭。 Mini Cooper SE 之前公布了官方定價，最低從 27,900 歐元起算，美國售價約 29,900 美元。相比現有的三門款，只貴了一成左右。然而，三年後，中國消費者將有機會買到最便宜的電動 Mini。 電動 Mini Cooper SE 最低價是 27,900 歐元，扣掉全額補助最低可以到 24,400 歐元。 BMW 集團與中國長城汽車集團於 2018 年宣布，將組建合資公司光束汽車，投入在中國的電動車生產計畫，而現在他們正式宣布啟動計畫，於江蘇張家港打造一個新工廠，全部投入電動車的製造，包括了 Mini Cooper SE 和其他長城汽車旗下的電動車。 目前的電動 Mini 只在英國牛津工廠製造，不難想像當產能轉移到中國後，Mini Cooper SE 的價格將有機會進一步調降，來競爭全球最大的電動車市場。這座屬於合資公司光束汽車的新工廠，採用一個新的產銷模式，由 BMW 和長城共同合作開發、設計、製造新產品，但是銷售通路完全沿用原本的品牌渠道。 換句話說，2020 年到 2022 年銷售的電動 Mini，將會是英國製造，而 2022 年後就會有中國製造版本開賣，考量到 Mini 在中國每年約有 30 萬輛的銷售額，同時油電版的 Coutryman 銷量更佔了全球將近五分之一，無怪乎 BMW 會想在最接近主要市場的地方蓋工廠囉。 外型完美復刻油車版 最後，簡單介紹一下 Mini Cooper SE 這台車。Mini 在電動化的路上，盡力保持著跟經典造型一致的設計，畢竟大家愛的就是它的設計。電動版的 Mini 車頭、車身跟車屁股都多了一個黃色的插頭標誌，車頭的氣壩則變成封閉式設計，除此之外，幾乎看不出來差別，連馬達...
張貼留言
閱讀完整內容