溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了java棧與隊列如何實現的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇java棧與隊列如何實現文章都會有所收獲，下面我們一起來看看吧。
棧 (Stack)是一種后進先出(last in first off，LIFO)的數據結構
隊列(Queue)則是一種先進先出 (fisrt in first out，FIFO)的結構
棧是一種線性結構，與數組相比，棧對應的操作是數組的子集。
它只能從一端添加元素，也只能從一端取出元素(這一端稱之為棧頂)。
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)說明的是什么問題？
棧的實現可以通過 數組 或者 鏈表 實現，在這里我們使用 數組來實現上述接口。
在棧的設計中，用戶只關注棧頂元素存取和棧長度，因此設計代碼如下：
讀者可以使用 棧 這種數據結構去解決LeetCode上的第20號問題：有效的括號，也可以查看 每天一算：Valid Parentheses。
隊列也是一種線性數據結構，與數組相比，隊列對應的操作是數組的子集。
只能從一端 (隊尾) 添加元素，只能從另一端 (隊首) 取出元素。
隊列的應用可以在播放器上的播放列表，數據流對象，異步的數據傳輸結構(文件IO，管道通訊，套接字等)上體現，當然最直觀的的就是排隊了。
| 接口 | 說明 | 復雜度 |
|---|---|---|
| void enqueue(E e) | 入隊 | O(1) 均攤 |
| E dequeue() | 出隊 | O(n) |
| E getFront() | 獲取隊首元素 | O(1) |
| int getSize() | 獲取隊列元素個數 | O(1) |
| boolean isEmpty() | 判斷隊列是否為空 | O(1) |
入隊是從隊尾開始，有可能觸發resize，因此均攤下來是O(1)。出隊是在隊首，數組實現每次都要挪動所有元素,O(n)。
關于“java棧與隊列如何實現”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“java棧與隊列如何實現”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
