希望這篇文章能合你的胃口
大家在學習資料結構的時候應該都學習過堆疊和佇列，對他倆的原理應該很熟悉了，堆疊是先進后出，佇列是先進先出，下面我們通過這篇文章來幫助小伙伴們回憶一下堆疊和佇列的那些事，
閱讀完這篇文章你會有以下識訓，
了解堆疊和佇列的意義
了解堆疊和佇列的實作方式
學會中綴運算式轉后綴運算式
學會后綴運算式的運算
了解回圈佇列
這是堆疊
堆疊模型
堆疊（stack）是限制插入和洗掉只能在一個位置上進行的表，該位置是表的末端叫做堆疊的頂（top），對堆疊的基本操作有push(進堆疊)和pop(出堆疊),前者相當于插入，后者則是洗掉最后插入的元素，
堆疊的另一個名字是LIFO（先進后出）表，普通的清空堆疊的操作和判斷是否空堆疊的測驗都是堆疊的操作指令系統的一部分，我們對堆疊能做的基本上也就是push和pop操作，
注：該圖描述的模型只象征著push是輸入操作，pop和top是輸出操作
下圖表示進行若干操作后的一個抽象的堆疊，一般的模型是，存在某個元素位于堆疊頂，而該元素是唯一可見元素，
堆疊的實作
因為堆疊是一個表，因此能夠實作表的方法都可以實作堆疊，ArrayList和LinkedList都可以支持堆疊操作，
刷題時我們可以直接使用Stack類來進行創建一個堆疊，刷題時我們可以通過下列代碼創建一個堆疊，下面兩種方式哪種都可以使用，
Deque<TreeNode> stack = new LinkedList<TreeNode>();//型別為TreeNode
Stack<TreeNode> stack = new Stack<TreeNode>();
堆疊的應用
堆疊在現實中應用場景很多，大家在刷題時就可以注意到，很多題目都可以用堆疊來解決的，下面我們來說一個比較常用的情景，數字運算式的求值，
不知道大家是否還記得那句口令，先乘除，后加減，從左算到右，有括號的話就先算括號里面的，這是我們做小學數學所用到的，四則運算中括號也是其中的一部分，先乘除后加減使運算變的復雜，加上括號后甚之，那么我們有什么辦法可以讓其變的更好處理呢？波蘭數學家Jan ?ukasiewicz想到了一種不需要括號的后綴運算式，我們也將它稱之為逆波蘭表示，不用數學家名字命名的原因有些尷尬，居然是因為他的名字太復雜了，所以用了國籍來表示而不是姓名，所以各位小伙伴以后給孩子起名字的時候不要太復雜啊，
揚·武卡謝維奇（波蘭語：Jan ?ukasiewicz，1878年12月21日烏克蘭利沃夫 - 1956年2月13日愛爾蘭都柏林），波蘭數學家，主要致力于數理邏輯的研究，著名的波蘭表示法逆波蘭表示法就是他的研究成果，
中綴運算式轉為后綴運算式
我們通過一個例子，來說明如何將中綴運算式轉為后綴運算式，
例
中綴:9 + ( 3 - 1 ) * 3 + 10 / 2
后綴:9 3 1 - 3 * + 10 2 / +
規則
1.從左到右遍歷中綴運算式的每個數字和符號，若是數字就輸出（直接成為后綴運算式的一部分，不進入堆疊）
2.若是符合則判斷其與堆疊頂符號的優先級，是右括號或低于堆疊頂元素，則堆疊頂元素依次出堆疊并輸出，等出堆疊完畢，當前元素入堆疊，
3.遵循以上兩條直到輸出后綴運算式為止，
老樣子大家直接看動圖吧簡單粗暴，清晰易懂
后綴運算式計算結果
中綴:9 + ( 3 - 1 ) * 3 + 10 / 2=20
后綴:9 3 1 - 3 * + 10 2 / +
后綴運算式的值也為20，那么我們來了解一下計算機是如何將后綴運算式計算為20的，
規則：
1.從左到右遍歷運算式的每個數字和符號，如果是數字就進堆疊
2.如果是符號就將堆疊頂的兩個數字出堆疊，進行運算，并將結果入堆疊，一直到獲得最終結果，
下面大家 繼續看動圖吧，
這是佇列
佇列模型
像堆疊一樣，佇列（queue）也是表，然而使用佇列時插入在一端進行而洗掉在另一端進行，遵守先進先出的規則，所以佇列的另一個名字是（FIFO），
佇列的基本操作是入隊（enqueue）:它是在表的末端(隊尾(rear)插入一個元素，出隊（dequeue）:出隊他是洗掉在表的開頭（隊頭(front)）的元素，
注：下面模型只象征著輸入輸出操作
具體模型
佇列的實作
佇列我們在樹的層次遍歷時經常使用，后面我們寫到樹的時候會給大家整理框架，佇列同樣也可以由陣列和LinkedList實作，刷題時比較常用的方法是
Queue<TreeNode> queue = new LinkedList<TreeNode>();
回圈佇列
回圈佇列的出現就是為了解決佇列的假溢位問題，何為假溢位呢？我們運用陣列實作佇列時，陣列長度為5，我們放入了[1,2,3,4,5],我們將1，2出隊，此時如果繼續加入6時，因為陣列末尾元素已經被占用，再向后加則會溢位，但是我們的下標0，和下標1還是空閑的，所以我們把這種現象叫做“假溢位”，
例如，我們在學校里面排隊洗澡一人一個格，當你來到澡堂發現前面還有兩個格，但是后面已經滿了，你是去前面洗，還是等后面格子的哥們洗完再洗？肯定是去前面的格子洗，除非澡堂的所有格子都滿了，我們才會等，
所以我們用來解決假溢位的方法就是后面滿了，就再從頭開始，也就是頭尾相接的回圈，我們把佇列的這種頭尾相接的順序存盤結構成為回圈佇列，
我們發現佇列為空時front == rear，佇列滿時也是front == rear，那么問題來了，我們應該怎么區分滿和空呢？
我們可以通過以下兩種方法進行區分，
1.設定標記變數flag;當front==rear 時且flag==0時為空，當front==rear且rear為1時且flag==1時為滿
2.當佇列為空時，front==rear,當佇列滿我們保留一個元素空間，也就是說，佇列滿時，陣列內還有一個空間，
例：
然后我們再根據以下公式則能夠判斷佇列滿沒滿了，
(rear+1)%queuesize==front
queuesize,代表佇列的長度，上圖為5，我們來判斷上面兩張圖是否滿，（4+1）%5==0，（2+1）%5==3
兩種情況都是滿的,over，
注：為了用動圖把邏輯整的清晰明了，十幾秒的動圖，就要整半個多小時，改進好幾遍，如果覺得圖片對你有幫助的話就點個贊和在看吧，
大家如果覺得這篇文章對大家有幫助的話，就請你將它轉發給需要的人吧，順便請大家點個關注和在看吧，創作不易，你們的支持對我真的幫助很大!每天都會為大家分享一道精選演算法題，從簡到難，我們一起堅持下去吧
順手點個在看呀同學
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/202237.html
標籤：其他