歡迎光臨
每天分享高質量文章

漫畫:如何用棧實現佇列?

(點擊上方公眾號,可快速關註)


來源:程式員小灰

—————  第二天  —————










————————————





棧的特點是先入後出,出入元素都是在同一端(棧頂):


入棧:



出棧:




佇列的特點是先入先出,出入元素是在不同的兩端(隊頭和隊尾):


入隊:



出隊:




既然我們擁有兩個棧,那麼我們可以讓其中一個棧作為佇列的入口,負責插入新元素;另一個棧作為佇列的出口,負責移除老元素。







佇列的主要操作無非有兩個:入隊和出隊。


在模擬入隊操作時,每一個新元素都被壓入到棧A當中。


讓元素1 “入隊”:






讓元素2 “入隊”:






讓元素3 “入隊”:






這時候,我們希望最先“入隊”的元素1“出隊”,需要怎麼做呢?


讓棧A中的所有元素按順序出棧,再按照出棧順序壓入棧B。這樣一來,元素從棧A彈出並壓入棧B的順序是3,2,1,和當初進入棧A的順序1,2,3是相反的:




此時讓元素1 “出隊”,也就是讓元素1從棧B彈出:




讓元素2 “出隊”:







讓元素4 “入隊”:






此時的出隊操作仍然從棧B彈出元素。


讓元素3 “出隊”:









讓元素4 “出隊”:







  1. private Stack<Integer> stackA = new Stack<Integer>();

  2. private Stack<Integer> stackB = new Stack<Integer>();


  3. /**

  4. * 入隊操作

  5. * @param element  入隊的元素

  6. */

  7. public void enQueue(int element) {

  8.    stackA.push(element);

  9. }


  10. /**

  11. * 出隊操作

  12. */

  13. public Integer deQueue() {

  14.    if(stackB.isEmpty()){

  15.        if(stackA.isEmpty()){

  16.            return null;

  17.        }

  18.        transfer();

  19.    }

  20.    return stackB.pop();

  21. }


  22. /**

  23. * 棧A元素轉移到棧B

  24. */

  25. private void transfer(){

  26.    while (!stackA.isEmpty()){

  27.        stackB.push(stackA.pop());

  28.    }

  29. }


  30. public static void main(String[] args) throws Exception {

  31.    StackQueue stackQueue = new StackQueue();

  32.    stackQueue.enQueue(1);

  33.    stackQueue.enQueue(2);

  34.    stackQueue.enQueue(3);

  35.    System.out.println(stackQueue.deQueue());

  36.    System.out.println(stackQueue.deQueue());

  37.    stackQueue.enQueue(4);

  38.    System.out.println(stackQueue.deQueue());

  39.    System.out.println(stackQueue.deQueue());

  40. }





推薦閱讀(點擊圖片可跳轉閱讀)


【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂

© 2021 知識星球   网站地图