跳到主要內容

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

目錄

  • 一、背景

  • 二、概念

    • 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: 用隊列實現棧，用棧實現隊列，聽起來有點繞，都搞懂了就掌握了精髓！

留言

張貼留言

這個網誌中的熱門文章

Python 併發總結，多線程，多進程，異步IO

1 測量函數運行時間 import time def profile(func): def wrapper(*args, ** kwargs): import time start = time.time() func( *args, ** kwargs) end = time.time() print ' COST: {} ' .format(end - start) return wrapper @profile def fib(n): if n<= 2 : return 1 return fib(n-1) + fib(n-2 ) fib( 35 )   2 啟動多個線程，並等待完成   2.1 使用threading.enumerate() import threading for i in range(2 ): t = threading.Thread(target=fib, args=(35 ,)) t.start() main_thread = threading.currentThread() for t in threading.enumerate(): if t is main_thread: continue t.join()   2.2 先保存啟動的線程 threads = [] for i in range(5 ): t = Thread(target=foo, args= (i,)) threads.append(t) t.start() for t in threads: t.join()   3 使用信號量，限制同時能有幾個線程訪問臨界區 from threading import Semaphore import time sema = Semaphor...
張貼留言
閱讀完整內容

高雄十大包子名店出爐

, 圖文：吳恩文 高雄包子大賽落幕了，我只能就我個人意見， 介紹一下前十名這些包子，但是不能代表其他四位評審的意見，雖然身為評審長，我通常不會第一個表示意見，以免影響其他評審， 我主要工作是負責發問。   這次參賽的素包子很少，而且都不夠細致，又偏油，我不愛， 但是第一名的甜芝麻包－熔岩黑金包，竟然是素食得名－ 漢來蔬食巨蛋店。   這包子賣相太好，竹炭粉的黑色外皮刷上金粉，一上桌，眾人驚呼， 搶拍照，內餡是芝麻餡，混一點花生醬增稠，加入白糖芝麻油， 熔岩爆漿的程度剛剛好，我一直以為芝麻要配豬油才行、 但是選到好的黑芝麻油一樣不減香醇， 當下有二位評審就想宅配回家。   尤其特別的是，黑芝麻餡室溫易化，師傅必須要輪班躲在冷藏室內， 穿著大外套才能包，一天包不了多少，我笑說，漢來美食，集團餐廳那麼多，實力雄厚，根本是「 奧運選手報名參加村裡運動會」嘛，其他都是小包子店啊， 但是沒辦法，顯然大家都覺得它好看又好吃， 目前限定漢來蔬食高雄巨蛋店，二顆88元，可以冷凍宅配， 但是要排一陣子，因為供不應求，聽說，四月份， 台北sogo店開始會賣。   第二名的包子，左營寬來順早餐店，顯然平易近人的多，一顆肉包， 十塊錢，是所有參賽者中最便宜的，當然，個頭也小， 它的包子皮明顯和其他不同，灰灰的老麵，薄但紮實有嚼勁， 肉餡新鮮帶汁，因為打了些水，味道極其簡單，就是蔥薑，塩， 香油，薑味尤其明顯，是老眷村的味道， 而特別的是老闆娘是台灣本省人， 當年完全是依據眷村老兵的口味一步一步調整而來，沒有加什麼糖、 五香粉，胡椒粉，油蔥酥。就是蔥薑豬肉和老麵香，能得名， 應該是它的平實無華，鮮美簡單，打動人心。   這是標準的心靈美食，可以撫慰人心，得名之前，寛來順已經天天排隊，現在，恐怕要排更久了， 建議大家六七點早點上門。   第三名，「專十一」很神奇，我記得比賽最後， 大家連吃了幾家不能引起共鳴的包子，有些累，到了專十一， 就坐著等包子，其他評審一吃，就催我趕快試，我一吃， 也醒了大半。   它的包子皮厚薄適中，但是高筋麵粉高些，老麵加一點點酵母， 我心中，它的皮屬一屬二，至於餡又多又好吃，蛋黃還是切丁拌入， 不是整顆放，吃起來「美味、均衡、飽滿」。一顆二十元。   老闆是陸軍專科十一期畢業取名專十一，...
張貼留言
閱讀完整內容

韋伯連續劇終於更新 期待第一季順利完結

　　地球天文學界的跳票大王詹姆斯·韋伯空間望遠鏡 (James Webb Space Telescope，縮寫為 JWST)自 1996 年以來斷斷續續不按劇本演出的連續劇終於讓焦慮的觀眾們又等到了一次更新：五層遮陽罩測試順利完成。 裝配完成的韋伯望遠鏡與好夥伴遮陽罩同框啦。Credit: NASA 　　嚴格的測試是任何空間任務順利成功的重中之重。遮陽罩，這個韋伯望遠鏡異常重要的親密夥伴，要是無法正常運轉的話，韋伯的這一季天文界連續劇說不準就要一直拖更了。 　　詹姆斯·韋伯空間望遠鏡是歷史上造出的最先進的空間望遠鏡。它不僅是一架紅外望遠鏡，還具有特別高的靈敏度。但想要達到辣么高的靈敏度來研究系外行星和遙遠的宇宙童年，韋伯童鞋必須非常"冷靜"，體溫升高的話，靈敏度會大大折損。這個時候，遮陽罩就要大顯身手啦。 　　遮陽罩在韋伯的設計中至關重要。韋伯望遠鏡會被發射到拉格朗日 L2 點，運行軌道很高，遠離太陽、地球與月球。太陽是韋伯的主要熱量干擾的來源，其次是地球與月球。遮陽罩會有效阻斷來自這三大熱源的能量並保護韋伯維持在工作溫度正常運轉。這個工作溫度指的是零下 220 攝氏度(-370 華氏度；50 開爾文)。 上圖中我們可以看出，韋伯望遠鏡的配置大致可分為兩部分：紅色較熱的一面溫度為 85 攝氏度，藍色較冷的一面溫度達到零下 233 攝氏度。紅色的這部分中，儀器包括太陽能板、通信設備、計算機、以及轉向裝置。藍色部分的主要裝置包括鏡面、探測器、濾光片等。Credit: STSci. 　　遮陽罩的那一部分和望遠鏡的鏡面這部分可以產生非常極端的溫差。遮陽的這面溫度可以達到 110 攝氏度，足以煮熟雞蛋，而背陰處的部分溫度極低，足以凍結氧氣。 　　工程師們剛剛完成了五層遮陽罩的測試，按照韋伯在 L2 時的運行狀態安裝了遮陽罩。L2 距離地球約 160 萬公里。NASA 表示這些測試使用了航天器的自帶系統來展開遮陽罩，測試目前都已成功完成。韋伯望遠鏡遮陽罩負責人 James Cooper 介紹說這是遮陽罩"第一次在望遠鏡系統的电子設備的控制下展開。儘管這個任務非常艱巨，難度高，但測試順利完成，遮陽罩展開時的狀態非常驚艷"。 　　遮陽罩由五層 Kapton 製成。Kapton 是一種聚酰亞胺薄膜材料， 耐高溫絕...
張貼留言
閱讀完整內容