java棧與隊列如何實現

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

10余年的湘鄉網站建設經驗，針對設計、前端、開發、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都營銷網站建設的優勢是能夠根據用戶設備顯示端的尺寸不同，自動調整湘鄉建站的顯示方式，使網站能夠適用不同顯示終端，在瀏覽器中調整網站的寬度，無論在任何一種瀏覽器上瀏覽網站，都能展現優雅布局與設計，從而大程度地提升瀏覽體驗。創新互聯從事“湘鄉網站設計”,“湘鄉網站推廣”以來，每個客戶項目都認真落實執行。

棧與隊列

棧 (Stack)是一種后進先出(last in first off，LIFO)的數據結構
隊列(Queue)則是一種先進先出 (fisrt in first out，FIFO)的結構

棧 (Stack)

棧是一種線性結構，與數組相比，棧對應的操作是數組的子集。

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

Stack這種數據結構用途很廣泛，在計算機的使用中，大量的運用了棧，比如編譯器中的詞法分析器、Java虛擬機、軟件中的撤銷操作（Undo）、瀏覽器中的回退操作，編譯器中的函數調用實現等等。

棧的實現

接口	說明	復雜度
void push(E e)	向棧中加入元素	O(1) 均攤
E pop()	彈出棧頂元素	O(1) 均攤
E peek()	查看棧頂元素	O(1)
int getSize()	獲取棧中元素個數	O(1)
boolean isEmpty()	判斷棧是否為空	O(1)

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

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

在棧的設計中，用戶只關注棧頂元素存取和棧長度，因此設計代碼如下：

java棧與隊列如何實現

讀者可以使用棧這種數據結構去解決LeetCode上的第20號問題：有效的括號，也可以查看每天一算：Valid Parentheses。

隊列 Queue

隊列也是一種線性數據結構，與數組相比，隊列對應的操作是數組的子集。

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

隊列的應用可以在播放器上的播放列表，數據流對象，異步的數據傳輸結構(文件IO，管道通訊，套接字等)上體現，當然最直觀的的就是排隊了。

隊列的實現

接口	說明	復雜度
void enqueue(E e)	入隊	O(1) 均攤
E dequeue()	出隊	O(n)
E getFront()	獲取隊首元素	O(1)
int getSize()	獲取隊列元素個數	O(1)
boolean isEmpty()	判斷隊列是否為空	O(1)