java棧與隊列如何實現(xiàn)

這篇文章主要介紹了java棧與隊列如何實現(xiàn)的相關(guān)知識，內(nèi)容詳細(xì)易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇java棧與隊列如何實現(xiàn)文章都會有所收獲，下面我們一起來看看吧。

棧與隊列

1. 棧 (Stack)是一種后進(jìn)先出(last in first off，LIFO)的數(shù)據(jù)結(jié)構(gòu)

2. 隊列(Queue)則是一種先進(jìn)先出 (fisrt in first out，F(xiàn)IFO)的結(jié)構(gòu)

棧 (Stack)

棧是一種線性結(jié)構(gòu)，與數(shù)組相比，棧對應(yīng)的操作是數(shù)組的子集。

它只能從一端添加元素，也只能從一端取出元素(這一端稱之為棧頂)。

Stack這種數(shù)據(jù)結(jié)構(gòu)用途很廣泛，在計算機(jī)的使用中，大量的運(yùn)用了棧，比如編譯器中的詞法分析器、Java虛擬機(jī)、軟件中的撤銷操作（Undo）、瀏覽器中的回退操作，編譯器中的函數(shù)調(diào)用實現(xiàn)等等。

棧的實現(xiàn)

說明：push和pop操作在最后面進(jìn)行，有可能觸發(fā)resize，但均攤來算是O(1)的。
如果你想了解更多時間復(fù)雜度的分析，歡迎關(guān)注筆者后續(xù)要更新的文章：O(n)說明的是什么問題？

棧的實現(xiàn)可以通過 數(shù)組 或者 鏈表 實現(xiàn)，在這里我們使用 數(shù)組來實現(xiàn)上述接口。

在棧的設(shè)計中，用戶只關(guān)注棧頂元素存取和棧長度，因此設(shè)計代碼如下：

讀者可以使用 棧 這種數(shù)據(jù)結(jié)構(gòu)去解決LeetCode上的第20號問題：有效的括號，也可以查看 每天一算：Valid Parentheses。

隊列 Queue

隊列也是一種線性數(shù)據(jù)結(jié)構(gòu)，與數(shù)組相比，隊列對應(yīng)的操作是數(shù)組的子集。

只能從一端 (隊尾) 添加元素，只能從另一端 (隊首) 取出元素。

隊列的應(yīng)用可以在播放器上的播放列表，數(shù)據(jù)流對象，異步的數(shù)據(jù)傳輸結(jié)構(gòu)(文件IO，管道通訊，套接字等)上體現(xiàn)，當(dāng)然最直觀的的就是排隊了。

隊列的實現(xiàn)

入隊是從隊尾開始，有可能觸發(fā)resize，因此均攤下來是O(1)。出隊是在隊首，數(shù)組實現(xiàn)每次都要挪動所有元素,O(n)。

關(guān)于“java棧與隊列如何實現(xiàn)”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“java棧與隊列如何實現(xiàn)”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道。